maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$

Question

Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(which is not necessarily contiguous) (a[i],b[i]) such that if $$b[i]='<'$$ then $$a[i+1]<a[i]$$ and if $$b[i]='>'$$ then $$a[i+1] >a[i]$$.

For instance if the input is:

6
3 >
2 <
1 >
3 >
1 <
8 <

Then the output is 4 And the only maximum subsequence that we can choose is: 2 < 1 > 3 > 8 < because 1<2 3>1 and 8>3.

My idea: I tought about constructing the array dp[] such that dp[i] represents the maximum length of the longest sequence of (a[i],b[i]) with the given properties. I constructed it from the end like this:

$$b[i]='>'$$ then $$dp[i] = max(1+dp[j], i < j <= n \&\& nr[j] > nr[i])$$ and if $$b[i]='<'$$ then $$dp[i] = max(1+dp[j], i < j <= n \&\& nr[j] < nr[i])$$ The difficulty of the problem lies in finding the number $max(1+dp[j], i < j <= n \&\& nr[j] < nr[i])$ and $max(1+dp[j], i < j <= n \&\& nr[j] > nr[i])$ I implemented this by using a search tree which with all the elements of dp[] from $n$ to $i+1$ and then do the corresponding query depending on the sign. However, this solution turned up not to be very efficient since it takes more than 0.15 seconds for certain tests.

May somebody help solve this with a more efficient algorithm.

This is what I tried:

#include <iostream>

using namespace std;
int tree[400001],dp[101001],h[400001];
struct af
{
    int nr;
    char rs;
}v[101001];
int op(int x,int y)
{
    return x<y?y:x;
}
void update(int node, int left, int right, int pos, int val) {
    if (left == right) {
        tree[node] = val;
        h[node]=v[left].nr;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid)
        update(2 * node, left, mid, pos, val);
    else
        update(2 * node + 1, mid + 1, right, pos, val);
    tree[node] = op(tree[2 * node] , tree[2 * node + 1]);
}
int query(int node,int left,int right,int x,int y)
{
    if(x<=left && right<=y)
        return dp[node];
    int mid=(left+right)/2;
    int ans1=0,ans2=0;
    if(x<=mid) ans1=query(2*node,left,mid,x,y);
    if(y>mid) ans2=query(2*node+1,mid+1,right,x,y);
    return op(ans1,ans2);

}
int query1(int node, int left, int right, int x, int y,int z) {
    if(x <= left && right <= y && left==right)
    {
        
        if(h[node]>z && (h[node]!=0))
        {
            
            return tree[node];
        }
        else return 0;

    }
    int mid = (left + right) / 2;
    int ans1 = 0, ans2 = 0;

    if(x <= mid)
       {ans1 = query1(2 * node, left, mid, x, y,z);}
    if(y > mid)
       ans2 = query1(2 * node + 1, mid + 1, right, x, y,z);
    return op(ans1 , ans2);
}
int query2(int node, int left, int right, int x, int y,int z) {
    if(x <= left && right <= y && left==right)
    {
        if(h[node]<z && (h[node]!=0))
        return tree[node];
        else return 0;
    }
    int mid = (left + right) / 2;
    int ans1 = 0, ans2 = 0;
    if(x <= mid)
       ans1 = query2(2 * node, left, mid, x, y,z);
    if(y > mid)
       ans2 = query2(2 * node + 1, mid + 1, right, x, y,z);
    return op(ans1 , ans2);
}
void build(int node, int left, int right){
    if(left == right){
       tree[node] = dp[left];
       h[node]=v[left].nr;
       return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = op(tree[2 * node],tree[2 * node + 1]);
}
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>v[i].nr>>v[i].rs;
    
    dp[n]=1;
    update(1,1,n,n,1);
    for(int i=n-1;i>0;--i)
    {
            
        if(v[i].rs=='>')
        {
            
            dp[i]=query1(1,1,n,i+1,n,v[i].nr);
            dp[i]++;
        }
        if(v[i].rs=='<')
        {
            dp[i]=query2(1,1,n,i+1,n,v[i].nr);
            dp[i]++;
        }
        update(1,1,n,i,dp[i]);
    }
    cout<<tree[1];
    return 0;
}
 

Answer 1

You just have a sequence of boolean values, either true or false. How you calculate which ones are true or false is both trivial and irrelevant. So you need to find the longest possible subsequence of all true values.

May I suggest that your solution to this is bizarrely complex. There is no need for a search tree whatsoever. There is no need for any storage that is larger than O(1). There is no need for anything that seems to look like dynamic programming.

To find the subsequences:

1. Let i = 0. Let longest_l, longest_r = -1, -1
2. Starting at index i, find the first index l ≥ i with a a value "true". If there is no such index then go to Step 6.
3. Starting at index l, find the last consecutive index r with a value of "true".
4. If longest_l < 0 or r-l > longest_r - longest_l then replace longest_l with l, and longest_r with r.
5. Let i = r + 1 and go to Step 2.
6. If longest_l < 0 then all elements of the sequence are false. Otherwise the longest subsequence with "true" values is from longest_i to longest_j.

For n = 100101 with 800KB of data I'd expect this to be some milliseconds at most, plus the time of loading the data which may be more or a lot more.