Maximum Subarray Sum (Divide and Conquer)

Description

You are given an array containing 'n' elements. The array can contain both positive and negative integers. Determine the sum of the contiguous subarray with the maximum sum.

Consider the array {8, -9, 3, 6, 8, -5, 7, -6, 1, -3}.

The maximum subarray will be 3, 6, 8, -5, 7.

The maximum subarray sum will be 3+6+8+(-5)+7 = 19

Input Format:

The input contains the number of elements in the array, followed by the elements in the array.

Output Format:

The output contains the maximum subarray sum.

Sample Test Cases:

Input:

10 8 -9 3 6 8 -5 7 -6 1 -3

Output:

19

Input:

5 8 9 4 5 7

Output:

33

import java.util.Scanner;       class Source  {       static int maxSubArraySum(int arr[], int l, int h)       {                //Write code here to complete                }        public static void main(String[] args)       {           int n;          Scanner s = new Scanner(System.in);          n = s.nextInt();          int arr[] = new int[n];          for(int i = 0; i < n; i++)              arr[i] = s.nextInt();                        System.out.print(maxSubArraySum(arr, 0, n-1));       }   }