【leetcode】53. 最大子序和

题目内容

53. 最大子序和

思路分析

本题比较简单，可使用动态规划完成

方法一：动态规划

最大子序列和有以下特征：

nums[i]的最大子序列和等于max(nums[i-1]的最大子序列和加nums[i], nums[i])

因此nums[i]可利用nums[i-1]的计算结果，即可进行动态规划。

使用动态规划算出每个nums[i]的子序列和，最后取最大子序列和即可。

又因为只依赖上一个数字的计算结果，因此可以用一个pre变量来代替动态规划数组。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 动态规划
// 时间复杂度O(n)，只需遍历一次数组
// 空间复杂度O(1)，额外存储空间为常数
class Solution1 {
public:
    int maxSubArray(vector<int>& nums) {
      int max_sum = nums[0];
      int pre_max_sum = nums[0];

      for (int i = 1; i <nums.size(); ++i) {
         pre_max_sum = max(pre_max_sum+nums[i], nums[i]);
         max_sum = max(pre_max_sum, max_sum);
      }

      return max_sum;
    }
};

// 贪心算法
// 好吧感觉也并没有贪什么，和动态规划法差不多吧
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
       int max_sum = nums[0];
       int sum = nums[0];

       for (int i = 1; i<nums.size(); ++i) {
          sum = max(sum, 0);
          sum += nums[i];
          max_sum = max(sum, max_sum);
       }

       return max_sum;
    }
};

int main() {
   Solution s;
   int result;
   vector<int> input{ -2,1,-3,4,-1,2,1,-5,4 };
   result = s.maxSubArray(input);
   int a = 0;
}

收获

简单复习了下动态规划（但是遇到这种简单题还是不会用动态规划，还是得看答案？）