# CodeSprint 2 Problem: Subsequence Weighting

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;
}``````