Maximum Sub Array

Hi Geeks! Welcome to 100 Days of Leetcode Challenge.

In this article, we going to see about Maximum Subarray.

Day 29

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

Example:

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

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Approach

Using DP

public class Solution {
    public int MaxSubArray(int[] nums) {
        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.Length;i++)
        {
            if(dp[i-1] <= 0)
                dp[i] = nums[i];
            else if(dp[i-1] > 0){
                if(nums[i] + dp[i-1] <= 0)
                    dp[i] = nums[i];
                else
                    dp[i] = nums[i] + dp[i-1];
            }
            max = Math.Max(dp[i],max);
        }
        return max;
    }
}

It takes, O(n) time complexity and O(n) Space Complexity.

How can we reduce space complexity to O(1)? Can we able to solve that?

Yes, we can, by introducing two variables.

public class Solution {
    public int MaxSubArray(int[] nums) {
       
        int prev = nums[0];
        int current = 0;
        int max = nums[0];
        for(int i=1;i<nums.Length;i++)
        {
            if(prev <= 0)
                current = nums[i];
            else{
                if(nums[i] + prev <= 0)
                    current = nums[i];
                else
                    current = nums[i] + prev;
            }
            max = Math.Max(current,max);
            prev = current;
        }
        return max;
    }
}

Time Complexity : O(n)

Space Complexity: O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s