求数组中连续区间的和最大_求数组内小于2的最大连续区间,要求返回符合条件的区间位置和长度。

求数组中连续区间的和最大，并且打印该区间的下标。
最容易想到的是穷举法，和分治法。后来网上搜了一下发现动态规划来解决这个问题非常优雅，下面是动态规划法解决该问题的代码

public class a {
    public static void maxSubSequence(int[] a) {
        int curSum = 0;
        int maxSum = a[0];
        int start = 0, end = 0;
        int tempStart = 0;
        for (int i = 0; i < a.length; i++) {
            if (curSum == 0)
                tempStart = i;

            curSum += a[i];
            if (curSum > maxSum) {
                maxSum = curSum;
                end = i;
                start = maxSum < 0 ? end : tempStart;
            }

            if (curSum < 0)
                curSum = 0;

        }
        System.out.println("maxSum:" + maxSum + "/tstart:" + start + "/tend:"
                + end);
    }

    public static double random1(int start, int end) {
        return Math.ceil(Math.random() * (end - start) + start);
    }

    public static void main(String[] args) {
        int[] a = { 90, 9, 0, -7, 29, 7, -99, -72, 40, 63, 96, -92, 25, -53,
                -49, -6, -7, -37, 29, 39 };
        int[] b = { -3, -3, -1, -4, -7, -3, -1, -5 };
        maxSubSequence(a);
        maxSubSequence(b);

        // int start = -100;
        // int end = 100;
        // int[] arr = new int[20];
        // for (int i = 0; i < arr.length; i++) {
        // arr[i] = (int) random(start, end);
        // }
        // System.out.println(ArrayUtils.toString(arr));
        // maxSubSequence(arr);
    }
}