Maximum Subarray
Given an array of integers, find a contiguous subarray which has the largest sum.
Example
Given the array [−2,2,−3,4,−1,2,1,−5,3]
, the contiguous subarray [4,−1,2,1]
has the largest sum = 6
.
Note
The subarray should contain at least one number.
Challenge
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; } }