Given an array of n positive integers, write a program to find the maximum sum of increasing subsequence from prefix till i-th index and also including a given kth element which is after i, i.e., k > i .
Examples :
Input : arr[] = {1, 101, 2, 3, 100, 4, 5}
i-th index = 4 (Element at 4th index is 100)
K-th index = 6 (Element at 6th index is 5.)
Output : 11
So we need to calculate the maximum sum of subsequence (1 101 2 3 100 5) such that 5 is necessarily included in the subsequence, so answer is 11 by subsequence (1 2 3 5).Input : arr[] = {1, 101, 2, 3, 100, 4, 5}
i-th index = 2 (Element at 2nd index is 2)
K-th index = 5 (Element at 5th index is 4.)
Output : 7
So we need to calculate the maximum sum of subsequence (1 101 2 4) such that 4 is necessarily included in the subsequence, so answer is 7 by subsequence (1 2 4).
Prerequisite : Maximum Sum Increasing Subsequence
Simple Approach:
- Construct a new array containing elements till ith index and the kth element.
- Recursively calculate all the increasing subsequences.
- Discard all the subsequences not having kth element included.
- Calculate the maximum sum from the left over subsequences and display it.
Time Complexity: O(2n)
Efficient Approach: Use a dynamic approach to maintain a table dp[][]. The value of dp[i][k] stores the maximum sum of increasing subsequence till ith index and containing the kth element.
C++
// CPP program to find maximum sum increasing // subsequence till i-th index and including // k-th index. #include <bits/stdc++.h> #define ll long long int using namespace std; ll pre_compute(ll a[], ll n, ll index, ll k) { ll dp[n][n] = { 0 }; // Initializing the first row of the dp[][]. for (int i = 0; i < n; i++) { if (a[i] > a[0]) dp[0][i] = a[i] + a[0]; else dp[0][i] = a[i]; } // Creating the dp[][] matrix. for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { if (a[j] > a[i] && j > i) { if (dp[i - 1][i] + a[j] > dp[i - 1][j]) dp[i][j] = dp[i - 1][i] + a[j]; else dp[i][j] = dp[i - 1][j]; } else dp[i][j] = dp[i - 1][j]; } } // To calculate for i=4 and k=6. return dp[index][k]; } int main() { ll a[] = { 1, 101, 2, 3, 100, 4, 5 }; ll n = sizeof(a) / sizeof(a[0]); ll index = 4, k = 6; printf("%lld", pre_compute(a, n, index, k)); return 0; } |
Java
// Java program to find maximum sum increasing // subsequence tiint i-th index and including // k-th index. class GFG { static int pre_compute(int a[], int n, int index, int k) { int dp[][] = new int[n][n]; // Initializing the first row of // the dp[][]. for (int i = 0; i < n; i++) { if (a[i] > a[0]) dp[0][i] = a[i] + a[0]; else dp[0][i] = a[i]; } // Creating the dp[][] matrix. for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { if (a[j] > a[i] && j > i) { if (dp[i - 1][i] + a[j] > dp[i - 1][j]) dp[i][j] = dp[i - 1][i] + a[j]; else dp[i][j] = dp[i - 1][j]; } else dp[i][j] = dp[i - 1][j]; } } // To calculate for i=4 and k=6. return dp[index][k]; } // Driver code public static void main(String[] args) { int a[] = { 1, 101, 2, 3, 100, 4, 5 }; int n = a.length; int index = 4, k = 6; System.out.println( pre_compute(a, n, index, k)); } } // This code is contributed by Smitha. |
Python3
# Python program to find maximum # sum increasing subsequence till # i-th index and including k-th index. def pre_compute(a, n, index, k): dp = [[0 for i in range(n)] for i in range(n)] # Initializing the first # row of the dp[][] for i in range(n): if a[i] > a[0]: dp[0][i] = a[i] + a[0] else: dp[0][i] = a[i] # Creating the dp[][] matrix. for i in range(1, n): for j in range(n): if a[j] > a[i] and j > i: if dp[i - 1][i] + a[j] > dp[i - 1][j]: dp[i][j] = dp[i - 1][i] + a[j] else: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] # To calculate for i=4 and k=6. return dp[index][k] # Driver code a = [1, 101, 2, 3, 100, 4, 5 ] n = len(a) index = 4k = 6print(pre_compute(a, n, index, k)) # This code is contributed # by sahilshelangia |
C#
// C# program to find maximum // sum increasing subsequence // till i-th index and including // k-th index. using System; class GFG { static int pre_compute(int []a, int n, int index, int k) { int [,]dp = new int[n, n]; // Initializing the first // row of the dp[][]. for (int i = 0; i < n; i++) { if (a[i] > a[0]) dp[0, i] = a[i] + a[0]; else dp[0, i] = a[i]; } // Creating the dp[][] matrix. for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { if (a[j] > a[i] && j > i) { if (dp[i - 1, i] + a[j] > dp[i - 1, j]) dp[i, j] = dp[i - 1, i] + a[j]; else dp[i, j] = dp[i - 1, j]; } else dp[i, j] = dp[i - 1, j]; } } // To calculate for i=4 and k=6. return dp[index, k]; } // Driver code static public void Main () { int []a = {1, 101, 2, 3, 100, 4, 5}; int n = a.Length; int index = 4, k = 6; Console.WriteLine(pre_compute(a, n, index, k)); } } // This code is contributed by @ajit |
PHP
$a[0])
$dp[0][$i] = $a[$i] + $a[0];
else
$dp[0][$i] = $a[$i];
}
// Creating the dp[][] matrix.
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
if ($a[$j] > $a[$i] && $j > $i)
{
if (($dp[$i – 1][$i] + $a[$j]) >
$dp[$i – 1][$j])
$dp[$i][$j] = $dp[$i – 1][$i] +
$a[$j];
else
$dp[$i][$j] = $dp[$i – 1][$j];
}
else
$dp[$i][$j] = $dp[$i – 1][$j];
}
}
// To calculate for i=4 and k=6.
return $dp[$index][$k];
}
// Driver Code
$a = array( 1, 101, 2, 3, 100, 4, 5 );
$n = sizeof($a);
$index = 4;
$k = 6;
echo pre_compute($a, $n, $index, $k);
// This code is contributed by ita_c
?>
11
Time Complexity : O(n2)
Note: This approach is very useful if you have to answer multiple such queries of i and k because using the pre calculated dp matrix you can answer such query in O(1) time.
To try similar problem, give this article a read: Maximum product of an increasing subsequence
leave a comment
0 Comments