Maximum Subarray Sum (Divide and Conquer) Description You are given an array containing 'n' elements. The array
Fantastic news! We've Found the answer you've been seeking!
Question:
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)); } }
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Posted Date: