给定元素数的最大子数组

Answer 1

可以使用滑动窗口算法。

让我们举一个例子：

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

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

>

必须存储上一个窗口的减去元素的总和

如果减去的元素的和变为负数，则使其为0，否则保持原样

，每次在计算最大值=max(current_max,sum)时，将其更改为

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

仅此而已：）

#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";
}