给定一个数组，值可以为正、负和0，请返回累加和小于等于k的最长子数组长度。
思路
申请两个辅助数组，分别为 min_v[N] 和 map_idx[N]
min_v[i] 用于记录从i开始，往右累加的最小和
map_idx[i]由于记录，得到最小和的右边界的下标
min_v[i]的记录规则就是，从优往左进行遍历，如果累加和一直<0 那么就一直累加下去，这个条件下，map_idx[i]就一直记录之前的右边界。
如果发现相加之后大于零，那么就另起炉灶，从自己开始作为右边界的开始，以及往右累加的最小和。
在计算最长长度时，通过计算每个min_v[i]，可以进行整块的区间的相加，对应的下标也就可以通过map_idx[i]这个右边界进行跳跃。直到出现 sum >K 或者遍历结束。
以上面这种方式，我们从 第1,2,3,4 个位置分别开始计算，由于sum是累加和，
当从第2个开始时，直接去掉第一个的值就行，即 sum-=arr[1]，然后再计算，看看之前sum >K的情况是否有所改变。
代码
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<map>
using namespace std;int N;
int arr[1000]={0};void rand_arr(int N){srand((int)time(0));for(int i=0;i <N;i++){arr[i] = rand()%11 -2; //[-2,5]} // for(int i=0;i <N;i++){
// arr[i] = 5;
// }
// arr[N-1] = 2;
}void printarr(int N){for(int i=0;i <N;i++){printf("%d ",arr[i]);} printf("\n");
}void init(int N){rand_arr(N);printarr(N);
}//保存当前下标范围内的最小和
int min_v[1000]={0};
//记录当前下标和右边界
map<int,int> map_idx;
int main() { N = 10;init(N);int K = 2;map_idx[N-1] =N-1;min_v[N-1] = arr[N-1]; //从后往前累加 for(int i=N-2;i>=0;i--){if(min_v[i+1]<0){min_v[i] = min_v[i+1] + arr[i];map_idx[i] = map_idx[i+1];}else{min_v[i] = arr[i];map_idx[i] = i;}} //记录长度 int len =0;//记录目前右边界 int end=0;//记录目前的sum值 int sum=0;//因为右边界只会往右边挪，并且sum可以一直累加 for(int i=0;i<N;i++){while(sum+min_v[end]<=K && end<N){sum+=min_v[end];end = map_idx[end]+1;}//记录最大len len = max(len,end-i);//如果 end 和 i 相等的话，说明没有进入循环，即 sum根本没有加 sum -= end>i? arr[i]:0;//保持 end >=i; end = max(end,i+1);} printf("%d\n",len);return 0;
}