Given an array of n positive integers, write a program to find the maximum sum of increasing subsequence from prefix till ith 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
Explanation:
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
Explanation:
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
Naive 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)
Better 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++
// C++ program to find maximum sum increasing// subsequence till i-th index and including// k-th index.#include <bits/stdc++.h>#define ll long long intusing 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 till i-th index and including// k-th index.import java.io.*;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
# Python3 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 codea = [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 codestatic 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
<?php // PHP program to find maximum sum increasing// subsequence till i-th index and including// k-th index.function pre_compute(&$a, $n, $index, $k){ $dp = array_fill(0, $n, array_fill(0, $n, NULL)); // Initializing the first row of the dp[][]. for ($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 ($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?> |
Javascript
<script>// Javascript program to find maximum// sum increasing subsequence till // i-th index and including k-th index.function pre_compute(a, n, index, k){ let dp = new Array(n); for(let i = 0; i < n; i++) { dp[i] = new Array(n); for(let j = 0; j < n; j++) { dp[i][j] = 0; } } // Initializing the first row of // the dp[][]. for(let 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(let i = 1; i < n; i++) { for(let 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 codelet a = [ 1, 101, 2, 3, 100, 4, 5 ];let n = a.length;let index = 4, k = 6;document.write(pre_compute(a, n, index, k));// This code is contributed by mukesh07 </script> |
Output
11
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Efficient approach: This problem is basically finding of maximum sum of increasing sub-sequence up to the given index i that all the elements of the sub-sequence is less than the kth (index) element or arr[k]. Hence, find the Maximum Sum Increasing Subsequence.
For example: arr[] = {1, 101, 2, 3, 100, 4, 5}, index = 4; k = 6;
Now, we need to just find the max sum sub-sequence from the array till index 4 given that all the elements of that sub-sequence is less that arr[k] which is 5. Now, iterating through the array.
For i = 0; as 1 < 5; max increasing sub-sequence {1}, max = 1.
For i = 1; as 101 > 5; skip this entry. Max increasing sub-sequence {1}, max = 1.
For i = 2; as 2 < 5; max increasing sub-sequence {1, 2}, max = 3.
For i = 3; as 3 < 5; max increasing sub-sequence {1, 2, 3}, max = 6.
For i = 4; as 100 > 5; skip this entry. Max increasing sub-sequence {1, 2, 3}, max = 6.
as index = 4; hence stop here and answer will be max + a[k] = 6 + 5 = 11.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#include <limits.h>using namespace std;// Function to find the// maximum of two numbersint max(int a, int b){ if (a > b) { return a; } return b;}// Function to find the sumint pre_compute(int a[], int n, int index, int k){ // Base case if (index >= k) { return -1; } // Initialize the dp table int dp[index] = { 0 }; int i; // Initialize the dp array with // corresponding array index value for (i = 0; i <= index; i++) { dp[i] = a[i]; } int maxi = INT_MIN; for (i = 0; i <= index; i++) { // Only include values // which are less than a[k] if (a[i] >= a[k]) { continue; } for (int j = 0; j < i; j++) { // Check if a[i] is // greater than a[j] if (a[i] > a[j]) { dp[i] = dp[j] + a[i]; } // Update maxi maxi = max(maxi, dp[i]); } } // Incase all the elements in // the array upto ith index // are greater or equal to a[k] if (maxi == INT_MIN) { return a[k]; } return maxi + a[k]; // Contributed by Mainak Dutta}// Driver codeint main(){ int a[] = { 1, 101, 2, 3, 100, 4, 5 }; int n = sizeof(a) / sizeof(a[0]); int index = 4, k = 6; // Function call printf("%d", pre_compute(a, n, index, k)); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the// maximum of two numbersstatic int max(int a, int b){ if (a > b) { return a; } return b;} // Function to find the sumstatic int pre_compute(int a[], int n, int index, int k){ // Base case if (index >= k) { return -1; } // Initialize the dp table int[] dp = new int[index + 1]; int i; // Initialize the dp array with // corresponding array index value for(i = 0; i <= index; i++) { dp[i] = a[i]; } int maxi = Integer.MIN_VALUE; for(i = 0; i <= index; i++) { // Only include values // which are less than a[k] if (a[i] >= a[k]) { continue; } for(int j = 0; j < i; j++) { // Check if a[i] is // greater than a[j] if (a[i] > a[j]) { dp[i] = dp[j] + a[i]; } // Update maxi maxi = max(maxi, dp[i]); } } // Incase all the elements in // the array upto ith index // are greater or equal to a[k] if (maxi == Integer.MIN_VALUE) { return a[k]; } return maxi + a[k];} // Driver codepublic 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 rag2127 |
Python3
# Python3 program for the above approach# Function to find the sumdef pre_compute(a, n, index, k): # Base case if (index >= k): return -1 # Initialize the dp table dp = [0 for i in range(index)] # Initialize the dp array with # corresponding array index value for i in range(index): dp[i] = a[i] maxi = -float('inf') for i in range(index): # Only include values # which are less than a[k] if (a[i] >= a[k]): continue for j in range(i): # Check if a[i] is # greater than a[j] if (a[i] > a[j]): dp[i] = dp[j] + a[i] # Update maxi maxi = max(maxi, dp[i]) # Incase all the elements in # the array upto ith index # are greater or equal to a[k] if (maxi == -float('inf')): return a[k] return maxi + a[k]# Driver codea = [ 1, 101, 2, 3, 100, 4, 5 ]n = len(a)index = 4k = 6# Function callprint(pre_compute(a, n, index, k))# This code is contributed by rohitsingh07052 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the// maximum of two numbersstatic int max(int a, int b){ if (a > b) { return a; } return b;} // Function to find the sumstatic int pre_compute(int[] a, int n, int index, int k){ // Base case if (index >= k) { return -1; } // Initialize the dp table int[] dp = new int[index + 1]; int i; // Initialize the dp array with // corresponding array index value for(i = 0; i <= index; i++) { dp[i] = a[i]; } int maxi = Int32.MinValue; for(i = 0; i <= index; i++) { // Only include values // which are less than a[k] if (a[i] >= a[k]) { continue; } for(int j = 0; j < i; j++) { // Check if a[i] is // greater than a[j] if (a[i] > a[j]) { dp[i] = dp[j] + a[i]; } // Update maxi maxi = Math.Max(maxi, dp[i]); } } // Incase all the elements in // the array upto ith index // are greater or equal to a[k] if (maxi == Int32.MinValue) { return a[k]; } return maxi + a[k];} // Driver codestatic 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 avanitrachhadiya2155 |
Javascript
<script>// Javascript program for the above approach// Function to find the// maximum of two numbersfunction max(a, b){ if (a > b) { return a; } return b;}// Function to find the sumfunction pre_compute(a, n, index, k){ // Base case if (index >= k) { return -1; } // Initialize the dp table let dp = new Array(index + 1); dp.fill(0); let i; // Initialize the dp array with // corresponding array index value for(i = 0; i <= index; i++) { dp[i] = a[i]; } let maxi = Number.MIN_VALUE; for(i = 0; i <= index; i++) { // Only include values // which are less than a[k] if (a[i] >= a[k]) { continue; } for(let j = 0; j < i; j++) { // Check if a[i] is // greater than a[j] if (a[i] > a[j]) { dp[i] = dp[j] + a[i]; } // Update maxi maxi = Math.max(maxi, dp[i]); } } // Incase all the elements in // the array upto ith index // are greater or equal to a[k] if (maxi == Number.MIN_VALUE) { return a[k]; } return maxi + a[k];}// Driver codelet a = [ 1, 101, 2, 3, 100, 4, 5 ];let n = a.length;let index = 4, k = 6;document.write(pre_compute(a, n, index, k));// This code is contributed by divyeshrabadiya07</script> |
Output
11
Time Complexity: O( index2 )
Auxiliary Space: O( index )
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
