最大子序和

题目

思路

代码

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        int[] preSun = new int[len];
        preSun[0] = nums[0];
        int max = nums[0], min = nums[0];
        for (int i = 1; i < len; i++) {
            preSun[i] += (preSun[i - 1] + nums[i]);
            min = Math.min(min, preSun[i - 1]);
            max = Math.max(min < 0 ? preSun[i] - min : preSun[i], max);
        }
        return max;
    }
    //官方
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }