本文共 468 字，大约阅读时间需要 1 分钟。

题目

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

思路

DP是我一生之敌。

直接见这篇题解的思路，就比较清晰了

代码

class Solution {public:    int maxSubArray(vector
   
    & nums) {        int len = nums.size();        int res = nums[0];        for(int i = 1;i < len;i++){            if(nums[i-1] > 0){                nums[i] = nums[i] + nums[i-1];            }            if(nums[i] > res){                res = nums[i];            }        }                return res;    }};
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105784949 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！