53 最大子序和

难度

• 简单
• 中等
• 困难

  标签

  动态规划

  题目描述

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

  示例1：

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

  实例2：

  输入：nums = [1]
  输出：1

  题解

f[i] 表示 以 index = i 的元素结尾的 序列 的最大值。
则f[i] 有两种可能

• 只包含当前 i 的值，即i单独为一个序列
• 或者 f[i] = f[i-1] + array[i]，即i+前面的序列

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

  因为f[i] 其实只依赖 f[i-1],所以用一个pre标志f[i-1],优化后的代码如下，O(n)时间，O(1)空间

  class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        int max = nums[0];
        int pre = nums[0];
        for(int i = 1; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            max = Math.max(pre, max);
        }
        return max;
    }
  }