Maximum Subarray
Given an array of integers, find a contiguous subarray which has the largest sum.
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
The subarray should contain at least one number.
Can you do it in time complexity O(n)?
////similar as Minimum subarray
public class Solution { /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ public int maxSubArray(int[] nums) { // write your code int sum=nums[0]; int maxSum=nums[0]; for(int i=1;i<nums.length;i++) { if(sum<0) sum=0; sum=sum+nums[i]; maxSum=Math.max(maxSum,sum); } return maxSum; } }
[lintcode easy]Maximum Subarray
原文：http://www.cnblogs.com/kittyamin/p/4996504.html