PrintMaxSumIncreasingSubseq.java

/*
https://www.techiedelight.com/increasing-subsequence-with-maximum-sum/

*/

publicvoidprintMaxSumIncreasingSubseq(intA[]){
intn = A.length;

intsum[] = newint[n];
sum[0] = A[0];

//to store the subseq
List<List<Integer>> msis = newArrayList<Integer>();

for(inti=0;i<n;i++){
msis.add(newArrayList<Integer>());
 }

//Initialization
msis.get(0).add(A[0]);


for(inti=1 ; i < n ; i++){
for(intj=0 ; j < i ; j++){
//update the value of sum and the corresponding subseq
if(A[j] < A[i] && sum[i] < sum[j]){
sum[i] = sum[j];
msis.set(i, newArrayList<Integer>(msis.get(j)));
 }
 }
//add the last value to the sum
sum[i] += A[i];
msis.get(i).add(A[i]);
 }

intindex = 0;
for(inti=1;i<n;i++){
if(sum[index] < sum[i]) index = i;
 }

System.out.println("Maximum Sum : "+sum[index]);
System.out.println("Maximum Sum Increasing Subsequence : "+msis.get(index));

}

/*
Time & Space Complexity - O(n^2)
*/