Maximum Sub-Array:
A simple problem of figuring the maximum profit in investment over a given period can be calculated using maximum Maximum SubArray Problem.
In Maximum subarray problem, we require to find out the subarray of a given array having the maximum sum.
For example if the problem is
13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7
In the above array, we need to find the contiguous sequence that yields the maximum sum.
For this we need to find the sequence in the array to the right of middle element, the array to the left of the middle element and the array that crosses the middle element. In this 1st Part, we will present the code of finding the maximum subarray crossing the middle element.
Maximum Sub-Array Crossing Mid:
We find maximum subarray crossing the middle element by repetitive summing up the elements, First from mid towards the low, Second from the mid+1 towards the high. We output the sum of maximum subarray.
Maximum-SubArray Crossing Middle Element JAVA Program:
import java.util.Scanner;
public class FindMaxCrossingSubArray {
public static void main(String[] args) {
Scanner obj=new Scanner(System.in);
int n=obj.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=obj.nextInt();
}
int low=0;
int high=n-1;
int mid;
mid=low+high/2;
Max_Sub_Arr(arr, low, mid, high);
}
static void Max_Sub_Arr(int arr[],int low, int mid, int high){
int left_sum=arr[mid];
int sum;
int max_left;
sum=0;
for(int i=mid;i>=low;i--){
sum=sum+arr[i];
if(sum>left_sum){
left_sum=sum;
max_left=i;
}
}
int right_sum=arr[mid+1];
int max_right;
sum=0;
for(int j=mid+1;j<=high;j++){
sum=sum+arr[j];
if(sum>right_sum){
right_sum=sum;
max_right=j;
}
}
System.out.println(left_sum+right_sum);
}
}
