Dynamic Programming 17

Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order i.e. increasing subsequence.

Problem link :- click here

Code

import java.util.Scanner;

public class DynamicProgramming_17
{
	//Recursion
	static int maxSumIncreasingSubsequence(int arr[], int index, int last_num)
	{
		if(index >= arr.length)
			return 0;
		
		int with=0, with_out=0;
		if(arr[index] > last_num)
			with = arr[index] + maxSumIncreasingSubsequence(arr, index+1, arr[index] );
		with_out = maxSumIncreasingSubsequence(arr, index+1, last_num);
		
		return Math.max(with, with_out);
	}
	
	//DP
	static int maxSumIncreasingSubsequence(int[] arr)
	{
		int n = arr.length;
		int dp[] = new int[n];
		
		for(int i=0; i<n; i++)
			dp[i] = arr[i];
		
		int max = 0;
		for(int i=1; i<n; i++)
			for(int j=0; j<i; j++)
				if(arr[j] < arr[i])
				{
					int sum = dp[j] + arr[i];
					
					if(sum > dp[i])
						dp[i] = sum;
					
					if(sum > max)
						max = sum;
				}
		
		for(int x:dp)
			System.out.print(x + " ");
		
		return max;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		int arr[] = new int[n];
		
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		int ans = maxSumIncreasingSubsequence(arr);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}