K Negations Leetcode 솔루션 후 어레이 합계 최대화

난이도 쉽게
자주 묻는 질문 아마존
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 23

이 게시물은 K Negations Leetcode 솔루션 이후 어레이 합계 최대화에 있습니다.

문제 설명

In the problem”Maximize Sum Of Array After K 부정”배열 arr과 값 K가 주어집니다. 배열은 정수 값으로 구성됩니다. arr [i]의 값을 -arr [i] K 번으로 변경할 수 있습니다. i의 값을 반복 할 수 있습니다. 우리의 임무는이 방법을 K 번 적용하여 배열 합계를 최대화하고 수정 후 전체 배열 합계를 반환하는 것입니다.

arr = [2,-3,-1,5,-4], k=2
13

설명 :

K 부정 Leetcode 솔루션 후 어레이 합계 최대화

주어진 배열에서 -3을 3으로, -4를 4로 바꾸면 배열의 총합은 13이됩니다.

접근

우리의 임무는 배열 합계 최대화 배열은 양수 요소와 음수 요소로 구성되므로 다음 단계를 따릅니다.

  1. 먼저 가장 작은 값의 부호를 변경하기 위해 배열을 정렬합니다. 이것은 배열 합계.
  2.  이제 우리는 기껏해야 K의 부호를 바꿀 것입니다 음수.
  3. 한편 우리는 배열에 XNUMX이 있는지 여부도 추적합니다.
  4. 찾기 배열 합계.
  5. 최종 답변은 배열 합계 만약:
    1. K의 값은 XNUMX이됩니다.
    2. 배열에 XNUMX이 있습니다. 이런 식으로 XNUMX의 부호를 계속 변경합니다.
    3. 음수 값의 부호를 변경 한 후 K의 나머지 값은 짝수입니다. 이런 식으로 우리는 양수를 음수로 만든 다음 다시 양수로 만듭니다.
  6. 여기서 K 값은 음수이므로 기호를 변경합니다. 가장 작은 양수 K 번. 이것은 부정적으로 만들 것입니다. 이제 새 배열 합계를 반환합니다.

K 부정 처리 후 어레이 합계 최대화를위한 코드 Leetcode 솔루션

C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(),A.end());
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.size();i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero||K==0||K%2==0)
         return sum;
        else
            return sum-2*(*min_element(A.begin(),A.end()));       
    }
int main() 
{ 
 vector<int> arr = {2,-3,-1,5,-4}; 
 int k=2;
 cout<<largestSumAfterKNegations(arr,k)<<endl; 
 return 0;
}
13

자바 코드

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.length;i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero==1||K==0||K%2==0)
         return sum;
        else
            return sum-2*(Arrays.stream(A).min().getAsInt());      
    }
  public static void main(String[] args) {
    int [] arr = {2,-3,-1,5,-4}; 
    int k=2;
    int ans=  largestSumAfterKNegations(arr,k);
    System.out.println(ans);
  }
}
13

K Negations Leetcode 솔루션 후 어레이 합계 최대화의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 주어진 배열을 한 번만 통과하기 때문입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하기 때문입니다.

참조

코멘트를 남겨

Translate »