链接：https://leetcode.cn/problems/maximum-subarray/
之前题解的博客：https://tsuish.gitee.io/p/7a78
注：之后把这篇博客整理到hexo

我的代码

int max(int a,int b){
    return a>b?a:b;
}
int maxSubArray(int* nums, int numsSize){
    int dp[100001],res = nums[0];
    dp[0] = nums[0];
    for(int i=1;i<numsSize;i++){
        dp[i] = max(dp[i-1]+nums[i],nums[i]);
        res = max(res,dp[i]);
    }
    return res;
}

提交结果

执行结果：
通过
显示详情
添加备注

执行用时：
92 ms
, 在所有 C 提交中击败了
87.44%
的用户
内存消耗：
12.1 MB
, 在所有 C 提交中击败了
33.17%
的用户
通过测试用例：
209 / 209

思路

动态规划（英语：Dynamic programming，简称 DP），通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。
参考：https://zhuanlan.zhihu.com/p/365698607

此题思路：

定义一个状态数组dp[100001]，dp[i]表示第i个整数结尾的子数组中的最大值。

以第i个整数结尾的子数组分为两种情况：
1、和第i-1个整数结尾的子数组相连。
2、和第i-1个整数结尾的子数组不相连。即单独以第i个整数作为子数组。

状态转移方程：
dp[i] = max(dp[i-1]+nums[i],nums[i])

初始状态：dp[0] = nums[0]

注意，dp[i]表示nums[]中第i个整数结尾的子数组中的最大值，并不是nums[]中前i个整数的子数组的最大值。nums[]的前i个整数的子数组的最大值，是dp[]中前i（包括i）个元素的最大值。理解起来就是，nums[]的前i个整数的子数组的最大值，可能是以第k个（k<=i）整数结尾的子数组的最大值。

这句话说的很诗意：
coolBoy
2021-10-09
我觉得这道题目的思想是： 走完这一生 如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻。
出自：https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/1172041

参考：https://www.bilibili.com/video/BV1XR4y1j7Lo?t=317.8