Maximum Subset Sum is a problem of determining maximum subsequence of given inte
ID: 2247232 • Letter: M
Question
Maximum Subset Sum is a problem of determining maximum subsequence of given integer array A. That is when array A[] is given, find sum1=sigma_k = 0^1 A[k] = A[0] = A[1] = -2 + 11 = 9 sum2 = sigma_k = 1^3 A[k] = A[1] = A[2] + a[3] = 11 -4 + 13 = 20, etc Obviously sum2 is bigger than sum1 so sum1 cannot be maximum. Is there any other summation in array A that is bigger than sum2? If not then sum2 is maximum subset sum of given array A. Write a java code that determines maximum subset of given integer array A. a) What is the input size of your code? b) What is the run-time of your code? Justify your answerExplanation / Answer
Code:
import java.util.Scanner;
public class Chegg {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int arraySize = 0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter Size of an array: ");
arraySize = sc.nextInt();
int array[];
array = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
System.out.println("Enter " + (i + 1) + " element");
array[i] = sc.nextInt();
}
System.out.println("Given array elements");
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
int max_sum = Integer.MIN_VALUE;
int sum = 0;
System.out.println();
for (int i = 0; i < array.length; i++) {
sum = sum + array[i];
//this if condition is return true for first iteration
if (max_sum < sum)
{
max_sum = sum;
}
if (sum < 0) {
sum =0;
}
}
System.out.println();
System.out.println("Maximum Subset sum : "+max_sum);
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Running time in seconds " + totalTime/1000.0);
}
}
----------------
First we are taking array size from the user and then list of array elements upto that size.
After that this is the main logic to find the maximum sum of subsequent elements in the array
for (int i = 0; i < array.length; i++) {
sum = sum + array[i];
//this condition = true for first iteration
if (max_sum < sum)
{
max_sum = sum;
}
if (sum < 0) {
sum =0;
}
}
if array ={-9 10 3 8 }
for i=0 sum=-9 max-sum=sum sum<0 is true sum=0
for i=1 sum=10, max-sum=10 ,sum<0 false
for i=2 sum=10+3, max-sum=13, sum<0 false
for i=3 sum= 13+8, max-sum=21, sum<0 false
finally we will get output Maximum Subset sum : 21
eg:
Enter Size of an array:
4
Enter 1 element
-9
Enter 2 element
10
Enter 3 element
3
Enter 4 element
8
Given array elements
-9 10 3 8
Maximum Subset sum : 21
Running time in seconds 6.968
eg 2;
Enter Size of an array:
6
Enter 1 element
-9
Enter 2 element
6
Enter 3 element
5
Enter 4 element
-9
Enter 5 element
6
Enter 6 element
3
Given array elements
-9 6 5 -9 6 3
Maximum Subset sum : 11
Running time in seconds 5.789
in eg 1 "10 3 8" is the maximum subsequent set of given array.
in eg 2 "6 5" is the maximum set.