给定一个数组，值可以为正、负和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;
}