算法
算[0, w]区间长和求和过程中sum的[min, max]区间长的差
可以想象一个二维平面上的xOy坐标系:
1. 当a[i] > 0时, 图像斜向上生成一段斜线; 当a[i] > 0时, 图像斜向下生成一段斜线
2. 由此我们可以发现, 要计算初始值的位置有几种, 只需要看这个折线图在y $\in$ [0, w]这个区间内有几种不同的位置, 如下图所示, 只需平移图像让折线图落在[0, w]内即可
3. 其实有几种位置, 也就是[0, w]区间内刨去max - min剩下的地方
时间复杂度 $O(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n, w;
scanf("%d%d", &n, &w);
int sum = 0, mx = -1e9, mi = 0;
while (n -- )
{
int x;
cin >> x;
mx = max(mx, sum), mi = min(mi, sum);
sum += x;
}
mx = max(mx, sum), mi = min(mi, sum);
printf("%d\n", max(0, w - (mx - mi) + 1));
return 0;
}