Maximum Subarray

Array, Dynamic Programming

Given an integer array nums, find the subarray with the largest sum, and return its sum. Here, array can contains duplicate or nagative numbers also.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Solutions

Calculates the maximum sum ending at each position and ensures that this sum is the maximum seen so far.

Approach – Brute Force Technique

This algorithm works by calculating the sum of every possible subarray in the input array and updating maxSum whenever a larger sum is found.

Steps

1. Initialize: Set maxSum to the smallest possible integer. This variable will keep track of the maximum subarray sum we've encountered so far.

2. Iterate through the array: For each element in the array (index i from 0 to nums.Length - 1), calculate the sum of all subarrays starting at this position. This is done by another loop (index j from i to nums.Length - 1) that adds the current element (nums[j]) to sum.

3. Update maxSum: If sum is greater than maxSum, update maxSum with the value of sum. This step keeps track of the maximum sum of any subarray seen so far.

4. Return the result: After going through all the elements of the array and all possible subarrays, return maxSum which now contains the maximum sum of a subarray in the array.

public class Solution {
    public int MaxSubArray(int[] nums) {
        int maxSum = Int32.MinValue;
        for (int i = 0; i < nums.Length; i++) {
            int sum = 0;
            for (int j = i; j < nums.Length; j++) {
                sum += nums[j];
                maxSum = Math.Max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

Complexity

• Time Complexity: O(n^2)

• Auxiliary Space: O(1)

Approach – Dynamic Programming Technique

It calculates the maximum sum ending at each position and ensures that this sum is the maximum seen so far. If the sum becomes less than the current element, it means the sum of the previous subarray is negative and thus not worth keeping, so it starts a new subarray from the current position.

Steps

1. Initialize: Set maxCurrent and maxGlobal to the first element of the array. These variables will keep track of the maximum subarray sum we've encountered so far (maxGlobal) and the maximum sum ending at the current position (maxCurrent).

2. Iterate through the array: For each element from the second to the last (index i from 1 to nums.Length - 1), update maxCurrent to be the maximum of the current element (nums[i]) and the sum of the current element and the previous maxCurrent (maxCurrent + nums[i]). This step essentially says, "consider the current element as the start of a new subarray or include it in the sum of the existing subarray."

3. Update maxGlobal: If maxCurrent is greater than maxGlobal, update maxGlobal with the value of maxCurrent. This step keeps track of the maximum sum of any subarray seen so far.

4. Return the result: After going through all the elements of the array, return maxGlobal which now contains the maximum sum of a subarray in the array.

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        int maxCurrent = nums[0];
        int maxGlobal = nums[0];

        for (int i = 1; i < nums.Length; i++)
        {
            maxCurrent = Math.Max(nums[i], maxCurrent + nums[i]);
            if (maxCurrent > maxGlobal)
            {
                maxGlobal = maxCurrent;
            }
        }
        return maxGlobal;
    }
}

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(1)