LeetCode 53. Maximum Subarray

灰太狼 2023-06-04 04:58 124阅读 0赞

题目

简单DP

  1. class Solution {
  2. public:
  3.     int dp[100005];
  4.     int maxSubArray(vector<int>& nums) {
  6.         if(nums.size()==0)
  7.             return 0;
  9.         int ans = nums[0];
  10.         dp[0]=nums[0];
  11.         for(int i=1;i<nums.size();i++)
  12.         {
  13.             if(dp[i-1]<0)
  14.             {
  15.                 dp[i]=nums[i];
  17.                 ans=max(ans,dp[i]);
  19.             }
  20.             else
  21.             {
  22.                 dp[i]=dp[i-1]+nums[i];
  23.                 ans=max(ans,dp[i]);
  24.             }
  25.         }
  27.         return ans;
  28.     }
  29. };

转载于:https://www.cnblogs.com/dacc123/p/11427549.html

发表评论

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

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

相关阅读