Another problem from CodeSprint 2:

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence.

You are given a sequence A in which every element is a pair of integers i.e A = [ (a1, w1) , (a2, w2) ,…,(aN, wN)].

For a subseqence B = [ (b1, v1) , (b2, v2) , …. ,(bM, vM) ] of the given sequence:
We call it increasing if for every i ( 1 <= i < M ) , bi < bi+1 . Weight(B) = v1 + v2 + ... + vM . Task:
Given a sequence, output the maximum weight formed by an increasing subsequence

Input:
First line of input contains a single integer C. C test-cases follow. First line of each test-case contains an integer N. Next line contains a1, … , aN separated by a single space. Next line contains w1, … , wN separated by a single space.

Output:
For each test-case output a single integer number: Maximum weight of increasing subsequences of the given sequence.

Sample Input:
2
4
1 2 3 4
10 20 30 40
8
1 2 3 4 1 2 3 4
10 20 30 40 15 15 15 50
Sample Output:
100
110

First of all I created a recursive solution with backtracking:

#include <iostream>

#define max(a,b) (a>b?a:b)

int numbers[150000];
int weights[150000];

int maxWeight(int ref, int cur, int n){
    int take,dont;

    if (cur==n-1){
        if (numbers[cur]>numbers[ref])
            return weights[cur];
        else
            return 0;
    }

    take = dont = 0;

    if (ref==cur)
        take = weights[cur] + maxWeight(cur,cur+1,n);
    else if (numbers[cur]>numbers[ref])
        take = weights[cur] + maxWeight(cur, cur+1, n);

    dont = maxWeight(ref,cur+1,n);

    return max(take,dont);

}

int main(){
    int tests;
    int i,j,n;

    std::cin >> tests;

    for (i=0;i<tests;i++){
        std::cin >> n;
        for (j=0;j<n;j++)
            std::cin >> numbers[j];
        for (j=0;j<n;j++)
            std::cin >> weights[j];

        std::cout << maxWeight(0,0,n) << std::endl;
    }

    return 0;
}

It passed 1 out of 8 test cases, and reported time limit exceeded on the others. Here’s a solution that passed all test cases (coming from another user):

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <ctime>
#include <cstdio>
using namespace std;
const int N = 200000;
typedef long long int64;
typedef pair<int, int64> P;
int arr[N][2], c, n;

int main() {
    int cl = clock();
    for(scanf("%d", &c); c--; ) {
        scanf("%d", &n);
        for(int i = 0; i < n; i ++) {
            scanf("%d", &arr[i][0]);
        }
        for(int i = 0; i < n;  i ++) {
            scanf("%d", &arr[i][1]);
        }
        set<P> st;
        st.insert(P(0, 0));
        for(int i = 0; i < n; i ++) {
            set<P>::iterator it = st.lower_bound(P(arr[i][0], 0));
            it --;
            P new_item(arr[i][0], it->second + arr[i][1]);
            it ++;
            bool valid = true;
            vector<P> erase_list;
            while(it != st.end()) {
                if(it->first == arr[i][0] && it->second >= new_item.second) {
                    valid = false;
                    break;
                } else if(it->second <= new_item.second) {
                    erase_list.push_back(*it);
                    it ++;
                } else {
                    break;
                }
            }
            for(vector<P>::iterator it = erase_list.begin(); it != erase_list.end(); it ++) {
                st.erase(*it);
            }
            if(valid) {
                st.insert(new_item);
            }
        }
        cout << st.rbegin()->second << endl;
    }
    cerr << (clock() - cl) * 0.001 << endl;
    return 0;
}