题目链接
题目描述
实现代码
思路:由题意可知,第i个位置的字符串对应的最大连续子数组和肯定是与第i-1个位置的字符串对应的最大连续子数组和有关,关系就在于是否取当前值nums[i],什么时候取nums[i]呢,假设f[i]表示第i个位置的字符串对应的最大连续子数组和,那么当f[i-1] + nums[i] > nums[i]的时候,就取nums[i],否则,取nums[i]得到的结果比nums[i]本身还小,那取就没有必要了,其状态转移方程也可以写成如下形式:
f[i] = Math.max(f[i-1] + nums[i], nums[i]);
实现代码如下:
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if(len == 1) {
return nums[0];
}
int result = nums[0];
int current = nums[0];
for(int i=1; i<len; i++) {
if(current + nums[i] < nums[i]) {
current = nums[i];
} else {
current += nums[i];
}
result = Math.max(result, current);
}
return result;
}
}