# 前缀和
看到子数组的题目，就应该想到前缀和，为了最大化子数组的和，假设我们有前缀和s，为了让子数组和最大，我们应该找出[i, j]，使得s[j+1]-s[i]的差值最大：
ans=Max(s[j+1]−s[i]),j>=i
为了最大化s[j+1]-s[i]，遍历数组时记录最小的s[i]，然后枚举s[j+1]，求出最大的差值。
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
// 前缀和中首元素为0，因此这里min初始化为0
int min = 0;
int ans = nums[0];
for(int i = 0; i < nums.length; i++){
sum += nums[i];
ans = Math.max(sum-min, ans);
min = Math.min(sum, min);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 动态规划
dp表示以元素nums[i-1]结尾的子数组的和
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int dp = nums[0]; // 用dp存状态
int ans = nums[0];
for(int i = 1; i < n; i++){
// nums[i]加入dp代表的子数组的和与
// 单独nums[i]为子数组的和相比较，取较大者
dp = Math.max(nums[i], dp + nums[i]);
ans = Math.max(ans, dp);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14