이 게시물은 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
설명 :
주어진 배열에서 -3을 3으로, -4를 4로 바꾸면 배열의 총합은 13이됩니다.
접근
우리의 임무는 배열 합계 최대화 배열은 양수 요소와 음수 요소로 구성되므로 다음 단계를 따릅니다.
- 먼저 가장 작은 값의 부호를 변경하기 위해 배열을 정렬합니다. 이것은 배열 합계.
- 이제 우리는 기껏해야 K의 부호를 바꿀 것입니다 음수.
- 한편 우리는 배열에 XNUMX이 있는지 여부도 추적합니다.
- 찾기 배열 합계.
- 최종 답변은 배열 합계 만약:
- K의 값은 XNUMX이됩니다.
- 배열에 XNUMX이 있습니다. 이런 식으로 XNUMX의 부호를 계속 변경합니다.
- 음수 값의 부호를 변경 한 후 K의 나머지 값은 짝수입니다. 이런 식으로 우리는 양수를 음수로 만든 다음 다시 양수로 만듭니다.
- 여기서 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) 답을 저장하는 데 변수 만 사용하기 때문입니다.
