53. 最大子数组和

难度简单4599收藏分享切换为英文接收动态反馈

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

子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

解题思路：

遍历子串或者子序列的遍历方式：

  1. 以某个节点为开头的所有子序列。例如数组{1，2，3}的遍历结果为：[1]，[1，2]，[1，2，3]，[2]，[2，3]
  2. 根据子序列的长度。比如先遍历出子序列长度为1的子序列，再遍历出自序列长度为2的子序列。
  3. 以某个节点为结尾的子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历整个序列。例如以2为结束点的遍历结果为：[1,2]，[2]，以3为结束点的遍历结果为：[1，2，3]，[2，3]，[3]。

第一种遍历方式主要用于暴力解法。

第三种遍历方式因为可以产生递推关系，所以经常用于动态规划，这里的动态规划解法是以 先遍历出以某个节点为结束节点的所有子序列的 思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int maxSubArray(int[] nums) {

    /*
     *
     * 使用f(i)来表示以当前元素为结尾元素的最大子序列和，
     * 因为一共有n个元素，所以f(i)也有n个，所以需要创建一个长度为n的f数组，时间复杂度为O(N)，
     * 但是考虑到f(i) 只和 f(i - 1)相关，所以只需要使用一个变量保存f(i)即可，时间复杂度为O(1)
     * 则f(i）的更新规则为：当前值 和 f(i - 1) 加上当前值 中的最大值
     * 即状态转移方程为
     *           f(i)  =  max{(f(i-1) + nums[i]),nums[i]}
     * 只需计算出每个元素的f(i)，最后返回最大值即可
     *
     *
     *
     * */



    //使用sum代表f(i)，初始化为0
    int sum = 0;
    //ans 代表结果
    int ans = nums[0];

    for (int n : nums) {
        sum = Math.max(sum + n, n);
        ans = Math.max(sum,ans);
    }

    return ans;
}
  • 时间复杂度：O(N)，数组遍历
  • 空间复杂度：O(1)，f(i)