LeetCode 53 最大子序和

目录

• LeetCode 53 最大子序和
  • 目录
  • 1. 题目描述
    • 1.1. Limit
    • 1.2. Problem Description
    • 1.3. Sample Input 1
    • 1.4. Sample Output 1
    • 1.5. Source
  • 2. 解读
  • 3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

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

1.3. Sample Input 1

输入: [-2,1,-3,4,-1,2,1,-5,4]

1.4. Sample Output 1

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

1.5. Source

LeetCode 53 最大子序和

2. 解读

动态规划，用 $f(i)$ 代表以第 $i$ 个数结尾的连续子数组的最大和，递推方程如下。

$$f(i) = max(f(i - 1) + a_i, a_i)$$

---

代码参考自官方题解。

3. 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

---

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。