Skip to main content

Maximum sum increasing subsequence using dynamic programming

Here given code implementation process.

// 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
Last updated on by Kalkicode




Comment

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