53 Maximum Subarray ****

Given an integer arraynums, 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.

[1,3,-4,2]

Two ways, dp space complexity is O(n) then space O(1)

class Solution {
    // [-2,1,-3,4,-1,2,1,-5,4]
    // [-2,1,-2,4,3, ]
    public int maxSubArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int res = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i - 1] : 0);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

Using

Divide and Conquer

approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1)Divide the given array in two halves
2)Return the maximum of following three
….a)Maximum subarray sum in left half (Make a recursive call)
….b)Maximum subarray sum in right half (Make a recursive call)
….c)Maximum subarray sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.
Time Complexity:maxSubArraySum() is a recursive method and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + Θ(n)
The above recurrence is similar toMerge Sortand can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn).

The Kadane’s Algorithmfor this problem takes O(n) time. Therefore the Kadane’s algorithm is better than the Divide and Conquer approach, but this problem can be considered as a good example to show power of Divide and Conquer. The above simple approach where we divide the array in two halves, reduces the time complexity from O(n^2) to O(nLogn).

// A Divide and Conquer based Java 
// program for maximum subarray sum
// problem
import java.util.*;

class GFG {

    // Find the maximum possible sum in arr[] 
    // such that arr[m] is part of it
    static int maxCrossingSum(int arr[], int l,
                                int m, int h)
    {
        // Include elements on left of mid.
        int sum = 0;
        int left_sum = Integer.MIN_VALUE;
        for (int i = m; i >= l; i--)
        {
            sum = sum + arr[i];
            if (sum > left_sum)
            left_sum = sum;
        }

        // Include elements on right of mid
        sum = 0;
        int right_sum = Integer.MIN_VALUE;
        for (int i = m + 1; i <= h; i++)
        {
            sum = sum + arr[i];
            if (sum > right_sum)
            right_sum = sum;
        }

        // Return sum of elements on left
        // and right of mid
        return left_sum + right_sum;
    }

    // Returns sum of maxium sum subarray 
    // in aa[l..h]
    static int maxSubArraySum(int arr[], int l, 
                                      int h)
    {
    // Base Case: Only one element
    if (l == h)
        return arr[l];

    // Find middle point
    int m = (l + h)/2;

    /* Return maximum of following three 
    possible cases:
    a) Maximum subarray sum in left half
    b) Maximum subarray sum in right half
    c) Maximum subarray sum such that the 
    subarray crosses the midpoint */
    return Math.max(Math.max(maxSubArraySum(arr, l, m),
                    maxSubArraySum(arr, m+1, h)),
                    maxCrossingSum(arr, l, m, h));
    }

    /* Driver program to test maxSubArraySum */
    public static void main(String[] args)
    {
    int arr[] = {2, 3, 4, 5, 7};
    int n = arr.length;
    int max_sum = maxSubArraySum(arr, 0, n-1);

    System.out.println("Maximum contiguous sum is "+
                                         max_sum);
    }
}
// This code is contributed by Prerna Saini