leetcode：53. 最大子数组和

题目

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

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

示例：

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

解答 & 代码

解法一：动态规划

  • 动态规划数组 **preMax**：preMax[i] 代表以 nums[i] 为结尾的子数组的最大和
  • 状态转移方程：
    • preMax[i] = preMax[i - 1] + nums[i]，若preMax[i - 1] > 0
    • preMax[i] = nums[i]， 若preMax[i - 1] <= 0

又因为每个状态只和钱一个状态有关，因此不需要数组，只需要一个变量记录前一个状态值即可

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int result = INT_MIN;
  5.         int preMax = 0;
  6.         for(int i = 0; i < nums.size(); ++i)
  7.         {
  8.             preMax = preMax > 0 ? preMax + nums[i] : nums[i];
  9.             result = max(result, preMax);
  10.         }
  11.         return result;
  12.     }
  13. };

复杂度分析：设数组长为 N

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：124 ms, 在所有 C++ 提交中击败了 6.15% 的用户
  4. 内存消耗：66 MB, 在所有 C++ 提交中击败了 97.49% 的用户

解法二：分治法

[容易] 53. 最大子序和