# 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)
{
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
*/
}
}``````

#### 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()
{
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
*/
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)
{
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
*/
}
}``````

#### 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()
{
\$arr = array(1, 4, 3, 2, 3, 1);
\$n = count(\$arr);
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum    = 6
*/
}
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 arr = [1, 4, 3, 2, 3, 1];
var n = arr.length;
/*
arr = [1, 4, 3, 2, 3, 1]
------------------------
result = [1,2,3]
sum    = 6
*/
}
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() :
arr = [1, 4, 3, 2, 3, 1]
n = len(arr)
#    arr = [1, 4, 3, 2, 3, 1]
#    ------------------------
#    result = [1,2,3]
#    sum    = 6

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()
arr = [1, 4, 3, 2, 3, 1]
n = arr.length
#    arr = [1, 4, 3, 2, 3, 1]
#    ------------------------
#    result = [1,2,3]
#    sum    = 6
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
*/
}
}``````

#### 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 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
*/
}
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 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
*/
}``````

#### Output

``````  1  4  3  2  3  1
Sum : 6``````

## 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.