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)