PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
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()
{
int t=int.Parse(Console.ReadLine());
string[]now=Console.ReadLine().Split();
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;
}
}