Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
这道题就是求最大子串和
肯定是o(n)的时间和o(1)的空间
就是每次相加， 1、先判断是否全是非正数，如果是，那么直接返回最大的那个数。
2、然后每次加一个数，就这样依次加下去，如果nums[j]大于0，那么与result相比取大的。
2、如果此时的和小于0，那么舍去，并且将i置于此时j的下一位。
public class Solution {
public int maxSubArray(int[] nums) {
if( nums.length == 1)
return nums[0];
int result = nums[0],ans = nums[0];
int i = 0,j = 1;
for( int k = 0;k<nums.length;k++ ){
if( result < nums[k])
result = nums[k];
}
if( result <= 0 )
return result;
while( i<nums.length && j < nums.length ){
if( nums[i] < 0 ){
while( i<nums.length && nums[i]<0 )
i++;
if( i<nums.length )
ans = nums[i];
j = i+1;
}
else if( nums[j] >= 0 ){
ans+=nums[j];
j++;
result = result>ans?result:ans;
}else{
if( ans+nums[j] <= 0 ){
i = j+1;
j = j+2;
if( i<nums.length )
ans = nums[i];
}else{
ans+=nums[j];
j++;
}
}
}
return result;
}
}
然后发现是在写的是啰嗦。其实如下就可以
public class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
for(int i=1;i<nums.length;++i){
nums[i]=nums[i-1]<0 ? nums[i] : nums[i-1]+nums[i];
max = Math.max(max, nums[i]);
}
return max;
}
}
public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1)
return nums[0];
int preSum = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (preSum <= 0)
preSum = nums[i];
else {
preSum += nums[i];
}
if (preSum > max)
max = preSum;
}
return max;
}
}
leetcode 53 Maximum Subarray ----- java
原文：http://www.cnblogs.com/xiaoba1203/p/5719172.html