记一次动态规划优化的过程

优化题目：LeetCode--53. Maximum Subarray

本题也是我们熟知的最大子序列和，题目如下：

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

可能大家都已经知道最优解了，并且程序还特别的漂亮，比如我个人是比较喜欢这一版的：

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

但是，如果是第一次看到这个题目我想，上面这段程序的可读性是比较差的。下面我们将从最原始的动态规划开始，然后一步步优化：

首先，我们需要写出状态转移方程，我们记dp[i]表示【0-i】子数组最大和，那么dp[i] = max {dp[i - 1] + nums[i], nums[i]}。初始值dp[0] = nums[0]。

根据这个我们就可以写出：

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        
        for (int i = 1; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

        }
        
        return Arrays.stream(dp).max().getAsInt();
    }
}

但是，从状态转移图中我们可以看到，每一次状态转移，只与前一次的转态有关，所以我们没有必要保存所有的转态，只需要一个变量保存前一次的转态即可，这样我们就可以写出下面的代码了：

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

优化之后我们可以看到，本次的代码与上面最优代码也如出一辙了。