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

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;
    }
}

 

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

 

 

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
5.4K Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
5.4K
0
Would love your thoughts, please comment.x
()
x