示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。...,因为遇到负数一定是拉低总和
}
return result;
}
};
时间复杂度:O(n) 空间复杂度:O(1)
当然题目没有说如果数组为空,应该返回什么,...所以数组为空的话返回啥都可以了。...不少同学认为 如果输入用例都是-1,或者 都是负数,这个贪心算法跑出来的结果是0, 这是又一次证明脑洞模拟不靠谱的经典案例,建议大家把代码运行一下试一试,就知道了,也会理解 为什么 result 要初始化为最小负数了...那么先给出我的dp代码如下,有时间的录友可以提前做一做:
class Solution {
public:
int maxSubArray(vector& nums) {