最大子数组和
力扣题目链接
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
解题思路
前缀和：
- 首先一个最大前缀和，一个最小前缀和，两个的差值自然是最大子数组和；
- 每次计算前缀和的时候，更新答案和最小前缀和；
题解
class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size() == 1){return nums[0];}int ans = INT_MIN;int min_sum = 0;int pre_sum = 0;for(int n : nums){pre_sum += n;ans = max(ans, pre_sum - min_sum);min_sum = min(min_sum, pre_sum);}return ans;}
};
