지정된 요소 수를 가진 최대 부분 배열

Question

최대 부분 배열 문제는이 부분 배열의 요소 합이 가장 큰 1 차원 배열의 인접한 부분 배열을 찾으려고 시도합니다. 동적 프로그래밍을 사용하면 쉽게 해결할 수 있습니다.

그러나 하위 배열에 적어도 k 개의 요소가 있어야한다는 추가 제약 조건이있는 경우 어떻게 될까요? 그것을 해결하는 O (n) 또는 O (n * logn) 알고리즘이 있습니까?

Answer 1

Sliding Window 알고리즘을 사용할 수 있습니다. 현재 윈도우의 값을 계산하고 최대 있는지 확인해야 각각의 반복에서

Original array : 4 -2 6 -10 13 8 
Window size : k = 3 
maximum = -inf 

:

는 예를 들어 줄 수 있습니다.

1st window is : |4 -2 6| -10 13 8 
window sum = 8 
maximum = max(-inf , 8) = 8 

첫 번째 창 합 O(k) 2 창에 어떻게됩니까

있는 간단한 루프에 의해 계산되어야한다? 보시다시피, 이전 창에서 첫 번째 요소를 빼고 새 값을 합계에 추가하면 두 번째 창 합계를 얻을 수 있습니다. 즉 : 유사

2nd window is : 4 |-2 6 -10| 13 8 
Window sum = 8 - 4 + (-10) = -6 
maximum = max(8 , -6) = 8 

...

3rd window is : 4 -2 |6 -10 13| 8 
Window sum = -6 - (-2) + 13 = 9 
maximum = max(8 , 9) = 9 

4th window is : 4 -2 6 |-10 13 8| 
Window sum = 9 - 6 + 8 = 11 
maximum = max(9 , 11) = 11 

그래서 대답은 = 11

찾는 것,이 예제는 고정 창 크기입니다. 즉, 요소가 k 여야하는 최대 합계에 대해 질문하는 경우입니다. 질문에 적어도 k 개의 원소가 있으면. 다음 0을

• 당신은 감산 요소의 합이 마이너스가되면 이전의 윈도우의 차감 요소의 합
• 를 저장해야합니다 : 그것은 당신이 몇 가지 추가 작업을해야 할 요소가 K보다 클 수있다 그렇지 않으면

• 을 그대로 유지하고마다

  maximum = max(current_max , sum + subtracted_element's_sum)

,536,913,632에 maximum = max(current_max , sum) 그것을 변화를 계산할 때 의 10

모든 :)

복잡성 : O (n)이

C++ 구현 :

#include <bits/stdc++.h> 
using namespace std; 

int main(){ 
    int i,j,n,k,x,y; 
    cin>>n>>k; 
    vector<int>v; 
    for(i=0; i < n; i++) 
    { 
     cin>>x; 
     v.push_back(x); 
    } 
    int sum = 0, prev_sum = 0; 
    for(i=0;i<k;i++) // Calculating sum of first window 
     sum += v[i]; 
    int maximum = sum; 
    for(i = 1; i + k <= n; i++) 
    { 
     sum = sum - v[i-1] + v[i+k-1]; // Calculating sum of the next windows 
     prev_sum += v[i-1]; // Storing previous subtracted elements sum 
     if(prev_sum < 0) // Checking if previous sum becomes negative. If so then make it 0, otherwise skip 
      prev_sum = 0; 
     maximum = max(maximum, sum + prev_sum); // Saving maximum window sum 
    } 
    cout<<maximum<<"\n"; 
}