42. 连续子数组的最大和
1. 描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
2. 例子
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
3. 限制
- 1 <= arr.length <= $10^5$
- -100 <= arr[i] <= 100
4. 题解
n = i_nums.size()
时间复杂度: O(n)
空间复杂度: O(1)
class Solution
{
public:
// int maxSubArray(vector<int>& nums)
int maxSubArray(vector<int> &i_nums)
{
if(i_nums.empty()) return 0;
int maxSum = i_nums[0];
for(int i = 1, sum = i_nums[0]; i < i_nums.size(); i++)
{
sum = max(0, sum) + i_nums[i];
maxSum = max(maxSum, sum);
}
return maxSum;
}
};