차례
문제 정책
"중첩 된 연속 하위 배열의 최대 합 K"문제는 정수 배열이 제공된다는 것을 나타냅니다. 합이 최대가되도록 k-subarray의 최대 합을 구합니다. 이러한 k-subarray가 겹칠 수 있습니다. 따라서 다른 하위 배열 중에서 합이 최대가되도록 k-subarray를 찾아야합니다.
예
arr = {10,-10,20,30,-1,-2}, k = 2
50 50
설명 : 합계가 50 인 하위 배열에 최대 값이 있습니다. 그 후 우리가 왼쪽 또는 오른쪽 방향으로 가면 합계가 감소합니다. 그래서 우리가 왼쪽 방향으로 움직이면. -50과 10이 서로를 취소하기 때문에 다시 10의 합계를 얻을 수 있습니다. 그러나 우리가 올바른 방향으로 움직이면 우리의 합계는 계속 감소 할 것입니다. 그래서 이것은 우리가 얻을 수있는 최선의 대답입니다.
arr = {-1,-2,-3,-4}, k = 3
-1 -2 -3
설명 : 여기서 두 숫자 중 하나를 결합하면 더 나쁜 솔루션이 생성됩니다. 따라서 단일 번호를 선택하는 것이 더 좋습니다. 따라서 우리는 단일 숫자 -1 -2 -3을 선택합니다. 다른 조합은 우리에게 더 나쁜 결과를 줄 것입니다.
겹치는 연속 하위 배열의 최대 합 K에 대한 접근 방식
문제는 모든 부분 배열의 모든 합 중에서 k 개의 최대 합을 구하도록 요청합니다. 그래서 우리가 카단 연산. 문제를 해결할 수 없습니다. Kadane의 알고리즘을 사용하여 최대 합계를 찾을 수 있기 때문입니다. 그러나 그것은 두 번째 최대 값, 세 번째 최대 값 및 기타를 찾을 수 없습니다. Kadane의 알고리즘은 주로 첫 번째 최대 값을 찾는 데 초점을 맞추고 다음 최대 하위 배열 합계를 찾는 것을 목표로하지 않습니다. 여기서 우리는 minimumKSum과 maximumKSum의 두 배열을 만듭니다. 접두사 합계 배열을 사용하여 현재 인덱스에 대한 하위 배열의 합계를 찾습니다. 최소 배열 KSum은 하위 배열의 k 최소 합을 유지합니다. 배열 maximumKSum은 하위 배열의 k 최대 합을 유지합니다. 이제 각 인덱스에 대해 minimumKSum 및 maximumKSum 배열을 업데이트합니다. 배열을 통과 한 후 응답은 maximumKSum 내부에 저장됩니다.
암호
겹치는 연속 하위 배열의 K 최대 합을 찾는 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
void kMaxSubArrays(vector<int> input, int k)
{
int n = input.size();
vector<int> prefixSum(n);
prefixSum[0] = input[0];
for(int i=1;i<n;i++)
prefixSum[i] += prefixSum[i-1] + input[i];
vector<int> minimumKSum(k, INT_MAX);
minimumKSum[0] = 0;
vector<int> maximumKSum(k, INT_MIN);
vector<int> currentSum(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
if(prefixSum[i] < 0 && minimumKSum[j]==INT_MAX)
currentSum[j]=(-prefixSum[i])-minimumKSum[j];
else
currentSum[j] = prefixSum[i] - minimumKSum[j];
}
int j = 0;
for (int l = 0; l < k; l++) {
if (currentSum[j] > maximumKSum[l]) {
maximumKSum.insert(maximumKSum.begin() + l, currentSum[j]);
maximumKSum.erase(maximumKSum.begin() + k);
j++;
}
}
for (int j = 0; j < k; j++) {
if (prefixSum[i] < minimumKSum[j]) {
minimumKSum.insert(minimumKSum.begin() + j, prefixSum[i]);
minimumKSum.erase(minimumKSum.begin() + k);
break;
}
}
}
for (int element : maximumKSum)
cout<<element<<" ";
}
int main()
{
int inputSize;cin>>inputSize;
vector<int> input(inputSize);
for(int i=0;i<inputSize;i++)cin>>input[i];
int k;cin>>k;
kMaxSubArrays(input, k);
}
6 10 -10 20 30 -1 -2 2
50 50
겹치는 연속 하위 배열의 K 최대 합계를 찾는 Java 코드
import java.util.*;
class Main{
static void kMaxSubArrays(int input[], int k)
{
int n = input.length;
int prefixSum[] = new int[n];
prefixSum[0] = input[0];
for(int i=1;i<n;i++)
prefixSum[i] += prefixSum[i-1] + input[i];
int maximumKSum[] = new int[k];
for(int i=0;i<k;i++)
maximumKSum[i] = Integer.MIN_VALUE;
int minimumKSum[] = new int[k];
for(int i=0;i<k;i++)
minimumKSum[i] = Integer.MAX_VALUE;
minimumKSum[0] = 0;
int currentSum[] = new int[k];
for(int i=0;i<k;i++)
currentSum[i] = 0;
for (int i=0;i<n;i++) {
for (int j=0;j<k;j++) {
if(prefixSum[i] < 0 && minimumKSum[j]==Integer.MAX_VALUE)
currentSum[j]=(-prefixSum[i])-minimumKSum[j];
else
currentSum[j] = prefixSum[i] - minimumKSum[j];
}
int j = 0;
for (int l = 0; l < k; l++) {
if (currentSum[j] > maximumKSum[l]) {
maximumKSum[l] = currentSum[j];
for(int z = l+1;z<k;z++)
maximumKSum[z] = maximumKSum[z-1];
j++;
}
}
for (j = 0; j < k; j++) {
if (prefixSum[i] < minimumKSum[j]) {
minimumKSum[j] = prefixSum[i];
for(int z = j+1;z<k;z++)
minimumKSum[z] = minimumKSum[z-1];
break;
}
}
}
for(int i=0;i<k;i++)
System.out.print(maximumKSum[i]+" ");
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int inputSize = sc.nextInt();
int input[] = new int[inputSize];
for(int i=0;i<inputSize;i++)input[i] = sc.nextInt();
int k = sc.nextInt();
kMaxSubArrays(input, k);
}
}
6 10 -10 20 30 -1 -2 2
50 50
복잡성 분석
시간 복잡성 : O (k * N)
minimumKSum에 삽입하고 maximumKSum에 삽입하려면 O (k) 시간이 걸립니다. 그리고 우리는 배열의 각 요소를 반복하는 루프 내부에서이 프로세스를 수행하고 있습니다. 따라서 전체 시간 복잡성은 O (k * n).
공간 복잡성: 의 위에)
공간의 상한을 표시하는 inputArray에 입력을 저장합니다. 따라서 솔루션의 공간 복잡성은 선형입니다.
