Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Approach: For this question, we have two approaches. The first one is the divide and conquer method and the second one is Kadane’s Algorithm.

lets try Kadane’s Algorithm. The basic idea of this algorithm is is to look for all positive contiguous segments of the array. And keep track of maximum sum contiguous segment among all positive segments. Each time we get a positive sum compare it with max and update max if it is greater than max.

Code:

class Solution {
public int maxSubArray(int[] nums) {
int max=Integer.MIN_VALUE;
int end=0;
int l=nums.length;
for(int i=0;i<l;i++){
end=end+nums[i];
if(max<end){
max=end;
}
if(end<0){
end=0;

}
}
return max;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store