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