Maximum Subarray | Leetcode

Maximum Subarray | Leetcode

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

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

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Example 4:

Input:  nums = [-2,-4,-1,-5,-7]
Output: -1

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

 

Solution

[code lang=”java”]
class Solution {
public int maxSubArray(int[] nums)
{
/*If array is empty return 0*/
if(nums!= null && nums.length == 0)
{
return 0;
}

int max=nums[0],sum=0;
for(int i =0; i<nums.length; i++)
{

/* Case 1 : If sum is a negative number Say -3 and nums[i] = -2 . Assign smallest negative -2 as

Sum.
* Case 2: If sum is negative and nums[i] =1. Assign Sum = 1
*/
if(sum<nums[i] && sum<0)
{
sum = nums[i];
}
else
{
sum+= nums[i];
}
if(sum>max)
{
max = sum;
}
}
return max;
}
}
[/code]

 

Time Complexity

Loop is running for n times so O(n) where n is the length of the array

You Might also Like…

Best Time to Buy and Sell Stock

 

 

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *