Maximum sum increasing subsequence

Maximum sum increasing subsequence

  October 08, 2017    

---

Idea is to use dp

Base case = initial value of array

Check for every pair and if arr[i]>arr[j]
then check for previous processed dp[j] and check for new maximum value;


Code:

public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    int dp[]=new int[n];
    for(int i=0;i<n;++i)
   { arr[i]=ab.nextInt();
    dp[i]=arr[i];
       } 
       int max=dp[0];
    for(int i=1;i<n;++i)
    for(int j=0;j<i;++j)
    {
        if(arr[i]>arr[j] && dp[i]<dp[j]+arr[i])
        {
            dp[i]=dp[j]+arr[i];
            
        }
        max=Math.max(max,dp[i]);
    }
    System.out.println(max);
}
}


Code 2:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
     public static int maxInc(int arr[],int n)
     {
         int dp[]=new int[n];
         int max=Integer.MIN_VALUE;
         dp[0]=arr[0];
         for(int i=0;i<n;++i)
            {
                dp[i]=arr[i];
                for(int j=0;j<i;++j)
            {
                if(arr[j]<arr[i])
                dp[i]=Math.max(dp[i],arr[i]+dp[j]);
            }}
            for(int x:dp)
            {
                System.out.print(x+" ");
                max=Math.max(max,x);}
            return max;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(maxInc(arr,n));
}
}

}