[[EVD]]剑指Offer42.连续子数组的最大和

题目分析:[[EVD]] - 剑指 Offer 42. 连续子数组的最大和https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

简单描述:

• 一个或连续多个整数组成一个子数组,求所有子数组的和的最大值

限制&＃x1f6ab;

• 1 <&＃61; arr.length <&＃61; 10^5
• -100 <&＃61; arr[i] <&＃61; 100
• 时间复杂度为O(n)

示例:

输入: nums &＃61; [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大&＃xff0c;为 6。

解题思路:

思路:

• #动态规划DP
• dp操作
  • 只有一个决策,取不取当前数,使用dp[i]一维数组
    • dp[i]:以nums[i]为结尾的连续子数组最大和
    • 状态转移方程
      • dp[i] &＃61; max(dp[i-1]&＃43;nums[i],nums[i]);
  • 空间优化有2种思路
    • 1.直接将num数组作为dp数组使用
    • 2.使用辅助变量res维护最大值,防止中途断掉,maxx变量维护前一个节点的变动值

效率:

• 时间复杂度
• 空间复杂度

代码:

class Solution
{
public:/*因为必须是连续的,用一个辅助变量维护最大值*/int maxSubArray(vector &nums){int maxx &＃61; nums[0];int res &＃61; maxx;for (int i &＃61; 1; i };