leetcode-53. 最大子序和

JAVA解法

// 动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            // 返回加上 x 之后的与 x 本身大的那个
            pre = Math.max(pre + x, x);
            // 比较现在最新的最大值与上一次的最大值并返回大的那个
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

leetcode原题： 53. 最大子序和

解法分析

本题用动态规划，先假设 nums 数组中第一个为当前最大的和。对 nums 数组进行遍历，用 pre 变量加上每一个从 nums 数组提取出来的值，再取最大值作为 pre 当前的值，这一步可以理解为考虑是否加上下一个值。

然后再把 pre 与最初设置好的最大的和比较，并返回最大的，用的是 Math.max() 方法，加到最后即为最大和。