LeetCode53——Maximum Subarray

梦里梦外; 2022-08-09 12:56 268阅读 0赞

LeetCode53——Maximum Subarray

题意：

就是经典的动态规划问题。

这里直接给出公式：

dp[i]表示以nums[i]结尾的最大子序列和。

那么有：

dp[i]= max { dp[i-1] + nums[i] , nums[i] }

代码：

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

发表评论

表情：
评论列表 （有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读