This is a Java Program to find maximum subarray sum of an array. A subarray is a continuous portion of an array. The following program uses binary search approach to find the maximum subarray sum. The time complexity of the following program is O (n log n).

Here is the source code of the Java program to find maximum subarray sum. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

`/*`

`* Java Program to Find the maximum subarray sum using Binary Search approach`

`*/`

import java.util.Scanner;

public class MaxSubarraySum2

`{`

public static void main(String[] args)

`{`

Scanner scan = new Scanner(System.in);

System.out.println("Enter number of elements in array");

int N = scan.nextInt();

int[] arr = new int[ N ];

`/* Accept N elements */`

System.out.println("Enter "+ N +" elements");

for (int i = 0; i < N; i++)

arr[i] = scan.nextInt();

System.out.println("Max sub array sum = "+ max_sum(arr));

`}`

public static int max_sum(int[] arr)

`{`

return max_sum(arr, 0, arr.length - 1);

`}`

public static int max_sum(int[] arr, int low, int mid, int high)

`{`

int l = Integer.MIN_VALUE, r = Integer.MIN_VALUE;

for (int i = mid, sum = 0; i >= low; i--)

if ((sum += arr[i]) > l)

l = sum;

for (int i = mid +1, sum = 0; i <= high; i++)

if ((sum += arr[i]) > r)

r = sum;

return l + r;

`}`

public static int max_sum(int[] arr, int low, int high)

`{`

if (low == high)

return arr[low];

int mid = (low + high)/2;

int max1 = max_sum(arr, low, mid);

int max2 = max_sum(arr, mid + 1, high);

int max3 = max_sum(arr, low, mid, high);

return Math.max(Math.max(max1, max2), max3);

`}`

`}`

Enter number of elements in array 8 Enter 8 elements 20 5 3 -2 -1 -5 43 24 Max sub array sum = 87

**Sanfoundry Global Education & Learning Series – 1000 Java Programs.**

If you wish to look at all Java Programming examples, go to Java Programs.