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
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

  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);
	}
}

  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;
}

  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);
	}
}

  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)
}

  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();

  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();

  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()

   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()

  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);
	}
}

  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();

   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);
}

  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.