题目

未排序数组中累加和小于或等于给定值的最长子数组长度

java代码

package com.lizhouwei.chapter8;/** * @Description: 未排序数组中累加和小于或等于给定值的最长子数组长度 * @Author: lizhouwei * @CreateDate: 2018/5/8 20:14 * @Modify by: * @ModifyDate: */public class Chapter8_12 {    public int maxLength(int[] arr, int k) {        int sum = 0;        int[] helpArr = new int[arr.length + 1];        for (int i = 0; i < arr.length; i++) {            sum = sum + arr[i];            helpArr[i + 1] = Math.max(sum, helpArr[i]);        }        sum = 0;        int len = 0;        int maxLen = 0;        int index = 0;        for (int i = 0; i < arr.length; i++) {            sum = sum + arr[i];            index = bs(helpArr, sum - k);            len = index == -1 ? 0 : i - index + 1;            maxLen = Math.max(maxLen, len);        }        return maxLen;    }    public int bs(int[] helpArr, int num) {        int left = 0;        int right = helpArr.length - 1;        int mid = 0;        int res = -1;        while (left < right) {            mid = (left + right) / 2;            if (helpArr[mid] < num) {                left = mid + 1;            } else {                res = mid;                right = mid - 1;            }        }        return res;    }    //测试    public static void main(String[] args) {        Chapter8_12 chapter = new Chapter8_12();        int[] arr = {3, -2, -4, 0, 6};        System.out.print("数组 arr = {3, -2, -4, 0, 6}中和小于-2的最长子数组长度为:");        int maxLen = chapter.maxLength(arr, -2);        System.out.print(maxLen);    }}

结果