[0053] 最大子序和

• GitHub
• http://leetcode.xuezhisd.top/post/24baa144.html
• https://leetcode.com/problems/maximum-subarray
• https://leetcode-cn.com/problems/maximum-subarray

题目描述

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

Related Topics

数组

分治算法

动态规划

题目解析

• [请一句话描述题目…]

不确定性

方法一：动态规划

分析

• 最大连续子序列和，非常经典的问题。
• 当我们从头到尾遍历数组时，对于数组中的每个元素，有两个选择：加入之前的SubArray；或者另起炉灶。
  • 如果之前SubArray的和大于0，加入之前SubArray；
  • 如果之前SubArray的和小于等于0，另起炉灶。
• 状态转移方程： $$f(j) = max\left\{ {f(j - 1) + arr(j),{\rm{arr(j)}}} \right\}$$

$$result = \max \left\{ {f(j)} \right\}$$

其中，j为数组元素下标

思路

注意

知识点

• 数组
• 动态规划

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

  代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0]; // 第一个元素构成连续子数组的最大和
        for(int i=1; i<nums.size(); i++){ // 遍历所有元素
            nums[i] = max(nums[i-1]+nums[i], nums[i]); // 状态转移方程
            result = max(result, nums[i]); // 更新最大和
        }
        return result;
    }
};

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目