解析

动态规划

找一个转移方程，想到以当前元素结尾的最大子数组和，要么是当前元素，要么是当前元素加上前面的最大子数组和。

//! n,n -> 两次n循环，存maxPrefixSum数组占地n
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      int res=-0x3f3f3f;
        vector<int> maxPrefixSum(nums.size());
        maxPrefixSum[0] =nums[0];
        for(int i =1;i<nums.size();++i){
          if(maxPrefixSum[i-1]>0){
            maxPrefixSum[i] =nums[i]+maxPrefixSum[i-1];
          }else{
            maxPrefixSum[i]=nums[i];
          }
        }
        for (int i = 0; i < nums.size(); ++i) {
            res=max(res,maxPrefixSum[i]);
        }
        return res;
    }
};

2025-03-03 该篇文章被 HopoZ 打上标签: leetcode 动态规划归为分类: algo