Question

Accept a positive integer n from keyboard and then create an array or arraylist containing n random elements within the range [-n,n). Print out the random array or arraylist, and then find out and print out the number of inversions and the maximum subarray (index range of the maximum subarray along with the maximum subarray sum) in the array or arraylist using divide and conquer, respectively. For example, suppose we accept integer 6 from keyboard, then your program should create an array or arraylist con- taining 6 random elements within the range (-6,6]. Here we suppose the randomly generated array is (3,-1,3,2,1,-6). The number of inversions is 11. index range of the maximum subarray is (0,4and the maximum subarray sum is 10, which should be all returned by your program.

write a java program

Answer 1

Below is the code with Output:

import java.util.*;
public class Subaaray{
static int maximum(int a, int b, int c)
{
if (a>=b && a>=c)
return a;
else if (b>=a && b>=c)
return b;
return c;
}

// function to find maximum sum of subarray crossing the middle element
static int maxCrossingSubarray(int ar[], int low, int mid, int high)
{
/*
Initial leftSum should be -infinity.
*/
int leftSum = Integer.MIN_VALUE;
int sum = 0;
int i;

/*
iterating from middle
element to the lowest element
to find the maximum sum of the left
subarray containing the middle
element also.
*/
for (i=mid; i>=low; i--)
{
sum = sum+ar[i];
if (sum>leftSum)
leftSum = sum;
}

/*
Similarly, finding the maximum
sum of right subarray containing
the adjacent right element to the
middle element.
*/
int rightSum = Integer.MIN_VALUE;
sum = 0;

for (i=mid+1; i<=high; i++)
{
sum=sum+ar[i];
if (sum>rightSum)
rightSum = sum;
}

/*
returning the maximum sum of the subarray
containing the middle element.
*/
return (leftSum+rightSum);
}

// function to calculate the maximum subarray sum
static int maxSumSubarray(int ar[], int low, int high)
{
if (high == low) // only one element in an array
{
return ar[high];
}

// middle element of the array
int mid = (high+low)/2;

// maximum sum in the left subarray
int maximumSumLeftSubarray = maxSumSubarray(ar, low, mid);
// maximum sum in the right subarray
int maximumSumRightSubarray = maxSumSubarray(ar, mid+1, high);
// maximum sum in the array containing the middle element
int maximumSumCrossingSubarray = maxCrossingSubarray(ar, low, mid, high);

// returning the maximum among the above three numbers
return maximum(maximumSumLeftSubarray, maximumSumRightSubarray, maximumSumCrossingSubarray);
}

public static void main(String[] args) {
int n=0;
   System.out.println("Enter the value of n: ");
   Scanner sc = new Scanner(System.in);
   n=sc.nextInt();
   sc.close();
   int arr[]=new int[n];
       for(int i =0; i<n; i++){
       Random random = new Random();
int randomInt = random.nextInt(2*n) - n;
// int randomInt = (int)(n * Math.random());
arr[i]=randomInt;
}
for(int i =0; i<n; i++){
System.out.println(arr[i]);
}
  
   System.out.println("Maximum contiguous sum is "+
                                       maxSumSubarray(arr, 0, n-1));
/*int a[] = {6, 5, -2, 3, -1, -2, 0};
System.out.println(maxSumSubarray(a, 0, 6));*/
}
}

Output:

Enter the value of n: ANÚNA Maximum contiguous sum is 6

I hope you like the code and if you like please give it thumb's up.

Thanks