# LeetCode 53. Maximum Subarray

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: 6Explanation: [4,-1,2,1] has the largest sum = 6.`

Example 2:

`Input: nums = 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;
}
}

--

--