Maximum sum increasing subsequence using dynamic programming
In this article, we will explore the concept of finding the maximum sum increasing subsequence in an array using dynamic programming. We'll explain the problem statement, provide the pseudocode algorithm with detailed explanations, and discuss the resultant output. This algorithm has a time complexity of O(n^2).
Problem Statement
Given an array of integers, we are tasked with finding the maximum sum of an increasing subsequence within the array. An increasing subsequence is a sequence of numbers in the array such that each subsequent number is greater than the previous one. Our goal is to find the increasing subsequence with the maximum sum.
Pseudocode Algorithm
Here is the pseudocode algorithm to solve the maximum sum increasing subsequence problem:
// Function to find the maximum sum increasing subsequence
maxIncreasingSubsequence(arr[], n):
sum[n]
result = INT_MIN
// Get initial sum for each index
for i from 0 to n:
sum[i] = arr[i]
// Calculate maximum sum increasing subsequence
for i from 1 to n:
for j from 0 to i:
if sum[i] < (sum[j] + arr[i]) and arr[i] > arr[j]:
// Update sum
sum[i] = sum[j] + arr[i]
// Find the maximum sum
for i from 0 to n:
if result < sum[i]:
result = sum[i]
// Display the array and the maximum sum
display(arr, n)
print("Sum:", result)
Let's walk through the algorithm step by step:
- First, we initialize an array called "sum" to store the sum of increasing subsequences. We also set "result" to a very small value (INT_MIN) to track the maximum sum.
- Next, we iterate over the array from index 0 to n-1 and initialize each element of "sum" with the corresponding element from the input array.
- Then, we iterate over the array from index 1 to n-1. For each element at index i, we compare it with all previous elements (from index 0 to i-1) to find a previous element that is smaller than the current element. If such an element exists, we update the sum at index i by adding the current element to the sum at the previous index.
- After calculating all the sums, we iterate over the "sum" array to find the maximum sum. We update the "result" if we find a greater sum during the iteration.
- Finally, we display the input array and the maximum sum to the user.
Code Solution
// C Program
// Maximum sum increasing subsequence using dynamic programming
#include <stdio.h>
#include <limits.h>
// Function which is display array elements
void display(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
}
void maxIncreasingSubsequence(int arr[], int n)
{
int sum[n];
int result = INT_MIN;
// Get initial sum of a particular indexes
for (int i = 0; i < n; ++i)
{
sum[i] = arr[i];
}
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; j++)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
}
}
// Find result
for (int i = 0; i < n; i++)
{
if (result < sum[i])
{
// Find max sum
result = sum[i];
}
}
display(arr, n);
printf("\n Sum : %d\n", result);
}
int main()
{
int arr[] = {
1 , 4 , 3 , 2 , 3 , 1
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
maxIncreasingSubsequence(arr, n);
return 0;
}
Output
1 4 3 2 3 1
Sum : 6
// Java program for
// Maximum sum increasing subsequence using dynamic programming
public class Subsequence
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public void maxIncreasingSubsequence(int[] arr, int n)
{
int[] sum = new int[n];
int result = Integer.MIN_VALUE;
// Get initial sum of a particular indexes
for (int i = 0; i < n; ++i)
{
sum[i] = arr[i];
}
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; j++)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
}
}
// Find result
for (int i = 0; i < n; i++)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
}
display(arr, n);
System.out.print("\n Sum : " + result + "\n");
}
public static void main(String[] args)
{
Subsequence task = new Subsequence();
int[] arr = {
1 , 4 , 3 , 2 , 3 , 1
};
int n = arr.length;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
}
Output
1 4 3 2 3 1
Sum : 6
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
// C++ program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence
{
public:
// Function which is display array elements
void display(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
void maxIncreasingSubsequence(int arr[], int n)
{
int *sum = new int[n];
int result = INT_MIN;
// Get initial sum of a particular indexes
for (int i = 0; i < n; ++i)
{
sum[i] = arr[i];
}
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; j++)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
}
}
// Find result
for (int i = 0; i < n; i++)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
}
this->display(arr, n);
cout << "\n Sum : " << result << "\n";
}
};
int main()
{
Subsequence *task = new Subsequence();
int arr[] = {
1 , 4 , 3 , 2 , 3 , 1
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task->maxIncreasingSubsequence(arr, n);
return 0;
}
Output
1 4 3 2 3 1
Sum : 6
// Include namespace system
using System;
// Csharp program for
// Maximum sum increasing subsequence using dynamic programming
public class Subsequence
{
// Function which is display array elements
public void display(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public void maxIncreasingSubsequence(int[] arr, int n)
{
int[] sum = new int[n];
int result = int.MinValue;
// Get initial sum of a particular indexes
for (int i = 0; i < n; ++i)
{
sum[i] = arr[i];
}
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; j++)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
}
}
// Find result
for (int i = 0; i < n; i++)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
}
this.display(arr, n);
Console.Write("\n Sum : " + result + "\n");
}
public static void Main(String[] args)
{
Subsequence task = new Subsequence();
int[] arr = {
1 , 4 , 3 , 2 , 3 , 1
};
int n = arr.Length;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
}
Output
1 4 3 2 3 1
Sum : 6
package main
import "math"
import "fmt"
// Go program for
// Maximum sum increasing subsequence using dynamic programming
// Function which is display array elements
func display(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
func maxIncreasingSubsequence(arr[] int, n int) {
var sum = make([] int, n)
var result int = math.MinInt64
// Get initial sum of a particular indexes
for i := 0 ; i < n ; i++ {
sum[i] = arr[i]
}
for i := 1 ; i < n ; i++ {
for j := 0 ; j < i ; j++ {
if sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j] {
// Update sum
sum[i] = sum[j] + arr[i]
}
}
}
// Find result
for i := 0 ; i < n ; i++ {
if result < sum[i] {
// Get max sum
result = sum[i]
}
}
display(arr, n)
fmt.Print("\n Sum : ", result, "\n")
}
func main() {
var arr = [] int {1 , 4 , 3 , 2 , 3 , 1}
var n int = len(arr)
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
maxIncreasingSubsequence(arr, n)
}
Output
1 4 3 2 3 1
Sum : 6
<?php
// Php program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence
{
// Function which is display array elements
public function display($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
}
public function maxIncreasingSubsequence($arr, $n)
{
$sum = array_fill(0, $n, 0);
$result = -PHP_INT_MAX;
// Get initial sum of a particular indexes
for ($i = 0; $i < $n; ++$i)
{
$sum[$i] = $arr[$i];
}
for ($i = 1; $i < $n; ++$i)
{
for ($j = 0; $j < $i; $j++)
{
if ($sum[$i] < ($sum[$j] + $arr[$i]) && $arr[$i] > $arr[$j])
{
// Update sum
$sum[$i] = $sum[$j] + $arr[$i];
}
}
}
// Find result
for ($i = 0; $i < $n; $i++)
{
if ($result < $sum[$i])
{
// Get max sum
$result = $sum[$i];
}
}
$this->display($arr, $n);
echo("\n Sum : ".$result.
"\n");
}
}
function main()
{
$task = new Subsequence();
$arr = array(1, 4, 3, 2, 3, 1);
$n = count($arr);
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
$task->maxIncreasingSubsequence($arr, $n);
}
main();
Output
1 4 3 2 3 1
Sum : 6
// Node JS program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence
{
// Function which is display array elements
display(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
maxIncreasingSubsequence(arr, n)
{
var sum = Array(n).fill(0);
var result = -Number.MAX_VALUE;
// Get initial sum of a particular indexes
for (var i = 0; i < n; ++i)
{
sum[i] = arr[i];
}
for (var i = 1; i < n; ++i)
{
for (var j = 0; j < i; j++)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
}
}
// Find result
for (var i = 0; i < n; i++)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
}
this.display(arr, n);
process.stdout.write("\n Sum : " + result + "\n");
}
}
function main()
{
var task = new Subsequence();
var arr = [1, 4, 3, 2, 3, 1];
var n = arr.length;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
main();
Output
1 4 3 2 3 1
Sum : 6
import sys
# Python 3 program for
# Maximum sum increasing subsequence using dynamic programming
class Subsequence :
# Function which is display list elements
def display(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
def maxIncreasingSubsequence(self, arr, n) :
sum = [0] * (n)
result = -sys.maxsize
i = 0
# Get initial sum of a particular indexes
while (i < n) :
sum[i] = arr[i]
i += 1
i = 1
while (i < n) :
j = 0
while (j < i) :
if (sum[i] < (sum[j] + arr[i]) and arr[i] > arr[j]) :
# Update sum
sum[i] = sum[j] + arr[i]
j += 1
i += 1
i = 0
# Find result
while (i < n) :
if (result < sum[i]) :
# Get max sum
result = sum[i]
i += 1
self.display(arr, n)
print("\n Sum : ", result )
def main() :
task = Subsequence()
arr = [1, 4, 3, 2, 3, 1]
n = len(arr)
# arr = [1, 4, 3, 2, 3, 1]
# ------------------------
# result = [1,2,3]
# sum = 6
task.maxIncreasingSubsequence(arr, n)
if __name__ == "__main__": main()
Output
1 4 3 2 3 1
Sum : 6
# Ruby program for
# Maximum sum increasing subsequence using dynamic programming
class Subsequence
# Function which is display array elements
def display(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
end
def maxIncreasingSubsequence(arr, n)
sum = Array.new(n) {0}
result = -(2 ** (0. size * 8 - 2))
i = 0
# Get initial sum of a particular indexes
while (i < n)
sum[i] = arr[i]
i += 1
end
i = 1
while (i < n)
j = 0
while (j < i)
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
# Update sum
sum[i] = sum[j] + arr[i]
end
j += 1
end
i += 1
end
i = 0
# Find result
while (i < n)
if (result < sum[i])
# Get max sum
result = sum[i]
end
i += 1
end
self.display(arr, n)
print("\n Sum : ", result ,"\n")
end
end
def main()
task = Subsequence.new()
arr = [1, 4, 3, 2, 3, 1]
n = arr.length
# arr = [1, 4, 3, 2, 3, 1]
# ------------------------
# result = [1,2,3]
# sum = 6
task.maxIncreasingSubsequence(arr, n)
end
main()
Output
1 4 3 2 3 1
Sum : 6
// Scala program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence()
{
// Function which is display array elements
def display(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
def maxIncreasingSubsequence(arr: Array[Int], n: Int): Unit = {
var sum: Array[Int] = Array.fill[Int](n)(0);
var result: Int = Int.MinValue;
var i: Int = 0;
// Get initial sum of a particular indexes
while (i < n)
{
sum(i) = arr(i);
i += 1;
}
i = 1;
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (sum(i) < (sum(j) + arr(i)) && arr(i) > arr(j))
{
// Update sum
sum(i) = sum(j) + arr(i);
}
j += 1;
}
i += 1;
}
i = 0;
// Find result
while (i < n)
{
if (result < sum(i))
{
// Get max sum
result = sum(i);
}
i += 1;
}
display(arr, n);
print("\n Sum : " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
var arr: Array[Int] = Array(1, 4, 3, 2, 3, 1);
var n: Int = arr.length;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
}
Output
1 4 3 2 3 1
Sum : 6
import Foundation;
// Swift 4 program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence
{
// Function which is display array elements
func display(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
func maxIncreasingSubsequence(_ arr: [Int], _ n: Int)
{
var sum: [Int] = Array(repeating: 0, count: n);
var result: Int = Int.min;
var i = 0;
// Get initial sum of a particular indexes
while (i < n)
{
sum[i] = arr[i];
i += 1;
}
i = 1;
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
j += 1;
}
i += 1;
}
i = 0;
// Find result
while (i < n)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
i += 1;
}
self.display(arr, n);
print("\n Sum : ", result );
}
}
func main()
{
let task: Subsequence = Subsequence();
let arr: [Int] = [1, 4, 3, 2, 3, 1];
let n: Int = arr.count;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
main();
Output
1 4 3 2 3 1
Sum : 6
// Kotlin program for
// Maximum sum increasing subsequence using dynamic programming
class Subsequence
{
// Function which is display array elements
fun display(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
fun maxIncreasingSubsequence(arr: Array < Int > , n: Int): Unit
{
val sum: Array < Int > = Array(n)
{
0
};
var result: Int = Int.MIN_VALUE;
var i: Int = 0;
// Get initial sum of a particular indexes
while (i < n)
{
sum[i] = arr[i];
i += 1;
}
i = 1;
while (i < n)
{
var j: Int = 0;
while (j < i)
{
if (sum[i] < (sum[j] + arr[i]) && arr[i] > arr[j])
{
// Update sum
sum[i] = sum[j] + arr[i];
}
j += 1;
}
i += 1;
}
i = 0;
// Find result
while (i < n)
{
if (result < sum[i])
{
// Get max sum
result = sum[i];
}
i += 1;
}
this.display(arr, n);
print("\n Sum : " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Subsequence = Subsequence();
val arr: Array < Int > = arrayOf(1, 4, 3, 2, 3, 1);
val n: Int = arr.count();
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum = 6
*/
task.maxIncreasingSubsequence(arr, n);
}
Output
1 4 3 2 3 1
Sum : 6
Resultant Output
Let's apply the algorithm to an example to understand the resultant output. Consider the following input array:
arr = [1, 4, 3, 2, 3, 1]
After applying the algorithm, we get the following output:
Array: 1 4 3 2 3 1
Maximum Sum: 6
Explanation of the output:
The increasing subsequence with the maximum sum is [1, 2, 3], which has a sum of 6. The elements 1, 2, and 3 are chosen because they form an increasing subsequence with the maximum sum within the given array.
Finally
We learned how to find the maximum sum increasing subsequence using dynamic programming. We discussed the problem statement, provided the pseudocode algorithm, and explained the resultant output. The algorithm has a time complexity of O(n^2) due to the nested loops. By following this approach, we can efficiently solve the problem and find the maximum sum increasing subsequence in an array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment