DP #25. Maximum Sum Increasing Subsequence - mbhushan/dynpro GitHub Wiki
(25). Maximum Sum Increasing Subsequence
Given an array of n positive integers. Write a program to find the sum of
maximum sum subsequence of the given array such that the intgers in the subsequence
are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5},
then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10},
then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3},
then output should be 10
Formula:
if (A[i] < A[j]) {
T[j] = T[i] + A[j]
Parent[j] = i;
}
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
4 |
6 |
1 |
3 |
8 |
4 |
6 |
|
|
|
|
|
|
|
|
| MSIS0 |
4 |
6 |
1 |
3 |
8 |
4 |
6 |
| Parent0 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
|
|
|
|
|
|
|
|
| MSIS1 |
4 |
10 |
1 |
3 |
12 |
4 |
6 |
| Parent1 |
-1 |
0 |
-1 |
-1 |
0 |
-1 |
0 |
|
|
|
|
|
|
|
|
| MSIS2 |
4 |
10 |
1 |
3 |
18 |
4 |
6 |
| Parent2 |
-1 |
0 |
-1 |
-1 |
1 |
-1 |
0 |
|
|
|
|
|
|
|
|
| MSIS3 |
4 |
10 |
1 |
4 |
18 |
5 |
7 |
| Parent3 |
-1 |
0 |
-1 |
2 |
1 |
2 |
2 |
|
|
|
|
|
|
|
|
| MSIS4 |
4 |
10 |
1 |
4 |
18 |
8 |
10 |
| Parent4 |
-1 |
0 |
-1 |
2 |
1 |
3 |
3 |
|
|
|
|
|
|
|
|
| MSIS5 |
4 |
10 |
1 |
4 |
18 |
8 |
10 |
| Parent5 |
-1 |
0 |
-1 |
2 |
1 |
3 |
3 |
|
|
|
|
|
|
|
|
| MSIS6 |
4 |
10 |
1 |
4 |
18 (ans) |
8 |
14 |
| Parent6 |
-1 |
0 |
-1 |
2 |
1 |
3 |
5 |
|
|
|
|
|
|
|
|
| seq -> |
4 |
6 |
8 |
|
|
|
|
| index |
0 |
1 |
4 |
|
|
|
|
public int maxSumSubsequence(int [] A) {
if (A == null) {
return -1;
}
if (A.length < 1) {
return -1;
}
int len = A.length;
int [] T = new int[len];
for (int i = 0; i < T.length; i++) {
T[i] = A[i];
}
for(int i=1; i<len; i++) {
for (int j=0; j<i; j++) {
if (A[j] < A[i]) {
T[i] = Math.max(T[i], T[j] + A[i]);
}
}
}
int max = Integer.MIN_VALUE;
for (Integer x: T) {
if (x > max) {
max = x;
}
}
return max;
}
Max Sum Subsequence
- Time Complexity: O(n^2)
- Space Complexity: O(n)