Maximum Subarray

Leet code Link - https://leetcode.com/problems/maximum-subarray/description/

Complexity - Medium

Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

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.

Constraints:

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

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.

Solution

We can use brute force algorithm where we can have 2 loops and 3rd inner loop to calculate sum from i to j of above loops. This approach is very costly and takes O(n^3).

Instead we can store the prefix sum and just add the num while moving the loop that way we only need 2 loops.

But there is even better approach where we can use two pointers and as we move the window decrement the window size if the prefix is negative. This way we gt rid of all the negative sum and leads to max value.

class Solution {
    public int maxSubArray(int[] nums) {
        int prefix= 0; int maxsum = Integer.MIN_VALUE;
        int l=0; int r =0;
        while(r<nums.length){
            if(prefix<0){
                prefix-=nums[l];
                l++;
                continue;
            }
            prefix+=nums[r];
            maxsum = Math.max(maxsum,prefix);
            r++;
        }
        return maxsum;
    }
}

Time complexity: O(N), where N is the length of nums.

We iterate through every element of nums exactly once.

Space complexity: O(1)

No matter how long the input is, we are only ever using 2 variables: currentSubarray and maxSubarray.

If they explicitely ask for other solution we can use divide and cnquer

class Solution {
    private int[] numsArray;

    public int maxSubArray(int[] nums) {
        numsArray = nums;

        // Our helper function is designed to solve this problem for
        // any array - so just call it using the entire input!
        return findBestSubarray(0, numsArray.length - 1);
    }

    private int findBestSubarray(int left, int right) {
        // Base case - empty array.
        if (left > right) {
            return Integer.MIN_VALUE;
        }

        int mid = Math.floorDiv(left + right, 2);
        int curr = 0;
        int bestLeftSum = 0;
        int bestRightSum = 0;

        // Iterate from the middle to the beginning.
        for (int i = mid - 1; i >= left; i--) {
            curr += numsArray[i];
            bestLeftSum = Math.max(bestLeftSum, curr);
        }

        // Reset curr and iterate from the middle to the end.
        curr = 0;
        for (int i = mid + 1; i <= right; i++) {
            curr += numsArray[i];
            bestRightSum = Math.max(bestRightSum, curr);
        }

        // The bestCombinedSum uses the middle element and the best
        // possible sum from each half.
        int bestCombinedSum = numsArray[mid] + bestLeftSum + bestRightSum;

        // Find the best subarray possible from both halves.
        int leftHalf = findBestSubarray(left, mid - 1);
        int rightHalf = findBestSubarray(mid + 1, right);

        // The largest of the 3 is the answer for any given input array.
        return Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf));
    }
}

Time complexity: O(N⋅logN), where N is the length of nums.

On our first call to findBestSubarray, we use for loops to visit every element of nums. Then, we split the array in half and call findBestSubarray with each half. Both those calls will then iterate through every element in that half, which combined is every element of nums again. Then, both those halves will be split in half, and 4 more calls to findBestSubarray will happen, each with a quarter of nums. As you can see, every time the array is split, we still need to handle every element of the original input nums. We have to do this logN times since that's how many times an array can be split in half.

Space complexity: O(logN), where N is the length of nums.

The extra space we use relative to input size is solely occupied by the recursion stack. Each time the array gets split in half, another call of findBestSubarray will be added to the recursion stack, until calls start to get resolved by the base case - remember, the base case happens at an empty array, which occurs after logN calls.