 # KQM16A - Editorial

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

EASY

# PREREQUISITES:

Dynamic Programming

# PROBLEM:

Given a sequence of numbers find the number of increasing subsequences in the array (need not be contiguous).

# QUICK EXPLANATION:

Start at each position in the array, one by one, and recursively go to the next higher valued position and keep incrementing counter for each sequence.

# EXPLANATION:

Start at each position in the array and increment counter by 1. Next send that position to a recursive function and recursively go to the next next position, again incrementing counter by 1 for each such encounter of positions with higher value. Also memoization can be done.

# SOLUTIONS:

Setter's Solution
``````			using System;
class some
{
public static int[]arr;
public static int[]dp;
public static void Main()
{
arr=new int[t];
dp=new int[t];
for(int i=0;i<t;i++)
{
arr[i]=int.Parse(now[i]);
}
int sum=0;
for(int i=0;i<t;i++)
{
sum+=solve(i)+1;
}
Console.WriteLine(sum);
}
public static int solve(int ind)
{
if(dp[ind]!=0)return dp[ind];
int sum=0;
for(int i=ind+1;i<arr.Length;i++)
{
if(arr[i]>arr[ind])
{
sum+=solve(i)+1;
}
}
return dp[ind]=sum;
}
}
``````