数组中累加和小于等于k的最长子数组

问题描述：

给定一个无序数组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;

}

数组中累加和小于等于k的最长子数组的相关教程结束。