[数据结构与算法]最大子序和

题目链接

最大子序和

题目描述

注意点

• 子数组是连续的
• 子数组最少包含一个元素

解答思路

• 采用动态规划判断到达某个位置时是将该点加入到前面的子数组中和更大还是重新以该点作为子数组的开始和更大
• 判断在某个位置时的最大值是否比当前搜索到的子数组的最大值更大，如果大于则覆盖最大值，反之继续向后搜索

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        //储存最大值
        int maxAns = nums[0];
        for (int x : nums) {
            //判断单独成为一段还是加入其前面那一段更大
            pre = Math.max(pre + x, x);
            //判断之前的最大值还是现在这一段的值更大
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

关键点

• 遍历到某个位置时，要先更新到经过结点时的最大和，再更新到该结点的子数组的最大和