Maximum Sum Increasing Subsequence Dynamic Programming

Problem: Given an array of numbers, Find an increasing subsequence with the maximum sum. Ex: {4,6,1,3,8,4,6} will give {4,6,8} with maximum sum of 18 Basic idea is to traverse the array left to right and check if previous values are smaller than the current value. If they are smaller they can be added to current value to get the sum for current element. If the sum is greater than the existing current sum, update the value.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public static int[] maxSumIncSubSeq(int[] n){ int[] t1 = new int[n.length]; int[] t2 = new int[n.length]; for(int i = 0; i < n.length; i++){ t1[i] = n[i]; t2[i] = i; } for(int i = 0; i < n.length; i++){ for (int j = 0; j <= i; j++){ if(n[j] < n[i] && t1[i] < n[i] + t1[j]){ t1[i] = n[i] + t1[j]; t2[i] = j; } } } int max = Integer.MIN_VALUE; int maxInd = -1; List<Integer> result = new ArrayList<Integer>(); for(int i = 0; i < n.length; i++){ if(max < t1[i]){ max = t1[i]; maxInd = i; } } System.out.println("Max is : " + max); while(maxInd >= 0){ result.add(n[maxInd]); if(maxInd == 0){ break; } maxInd = t2[maxInd]; } int [] r = new int[result.size()]; for(int i = 0; i < result.size(); i++){ r[i] = result.get(i); } return r; }