20200623-最大子序和.md

每天一道leetCode

信息卡片

• 时间：2020-06-23
• 题目链接：https://leetcode-cn.com/problems/maximum-subarray
• tag：动态规划 分治

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

参考答案

动态规划

• 这个用动态规划是很简单的，用a[i]代表数组第i项，f(i)代表以第i项结尾的连续子数组的和，动态规划转移方程就是f(i) = Math.max(f(i - 1) + a[i], a[i])

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        int pre = 0;
        int res = nums[0];
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(pre, res);
            
        }
        return res;
    }
}

分治-线性树

• 这个方法我能看明白就不错了。。点这里
• 用java重写了一下

class Solution {
    public int maxSubArray(int[] nums) {
        return get(nums, 0, nums.length - 1).mSum;
    }
    private Status get(int[] nums, int left, int right) {
        if (left == right) {
            return new Status(nums[left], nums[left], nums[left], nums[left]);
        }
        int m = (left + right) >> 1;
        Status lStatus = get(nums, left, m);
        Status rStatus = get(nums, m + 1, right);
        return pushUp(lStatus, rStatus);
    }

    private Status pushUp(Status lStatus, Status rStatus) {
        int lSum = Math.max(lStatus.lSum, lStatus.iSum + rStatus.lSum);
        int rSum = Math.max(rStatus.rSum, rStatus.iSum + lStatus.rSum);
        int iSum = lStatus.iSum + rStatus.iSum;
        int mSum = Math.max(Math.max(lStatus.mSum, rStatus.mSum), lStatus.rSum + rStatus.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    class Status {
        int lSum;
        int rSum;
        int mSum;
        int iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }
}