问题描述:
给定一个无序数组arr,其中元素可正、可负、可0,给定一个整数 k。求arr所有的子数组中累加和小于或等于k的最长子数组长度。例如:arr=[3,-2,-4,0,6],k=-2,相加和小于或等于-2的最长子数组为{3,-2,-4,0},所以结果返回4。
代码如下:
int getLessIndex(int arr[], int len, int num)
{
int low = ;
int high = len - ;
int mid = ;
int ret = -; while(low <= high)
{
mid = (low + high) / ;
if(arr[mid] >= num)
{
ret = mid;
high = mid - ;
}
else
{
low = mid + ;
}
} return ret;
} int maxLength(int arr[], int len, int k)
{
int *pSums = new int[len + ];
int sum = ;
pSums[] = sum; for(int i = ; i < len; ++i)
{
sum += arr[i];
pSums[i + ] = max(sum, pSums[i]);
} sum = ;
int ret = ;
int idx = ;
int dis = ;
for(int i = ; i < len; ++i)
{
sum += arr[i];
idx = getLessIndex(pSums, len, sum - k);
dis = (idx == - ? : i - idx + );
ret = max(ret, dis);
} delete[] pSums;
return ret;
}