Longest Increasing/Decreasing Subsequence

A lot of related problems:

• topCoder: thePriceIsRight
  
• topCoder: autoMarket
  
• topCoder: books
  
• UVa 111: history grading
  
• UVa 231: testing the catcher
  
• UVa 497: strategic Defense Initiative
  
• UVa 10051: Tower of Cubes
  
• UVa 10131: Is Bigger Smarter
  
• Hoj: online tutorial problem 117, Intercept Missiles

two basic dp algorithms

e.g.,

sequence: 1,6,2,3,5,4,7
algorithm 1: O(N^2)
a    1  2  3  4  5  6  7
---------------------------
 1  6  2  3  5  4  7
---------------------------
0|  1  1  1  1  1  1  1
1| (1) 2  2  2  2  2  2
2|  1 (2) 2  2  2  2  2
3|  1  2 (2) 3  3  3  3
4|  1  2  2 (3) 4  4  4 
5|  1  2  2  3 (4) 4  5
6|  1  2  2  3  4 (4) 5 <-            

algorithm 2: O(NlogN)
a    1  2  3  4  5  6  7
---------------------------
 1  6  2  3  5  4  7
---------------------------
0|  1
1|  1  6
2|  1  2
3|  1  2  3
4|  1  2  3  5
5|  1  2  3  4
6|  1  2  3  4  7 <-

topCoder: thePriceIsRight 

// longest increasing sequence (O(N^2)) 
vector<int> lis (vector<int> prices) {
 vector<int> len(prices.size(), 1); //length of the longest inc sequence up to i 
 vector<int> ways(prices.size(), 1); //how many ways of the lcs up to i 

 for(int i = 0; i < prices.size()-1; ++i) {
     for(int j = i+1; j < prices.size(); ++j)
         if(prices[j] > prices[i]) {
             if(len[j] < len[i] + 1) {
                 len[j] = len[i] + 1;
                 ways[j] = ways[i];
             }
             else if(len[j] == len[i]+1)
                 ways[j]+= ways[i];
         }
 }
 int maxv = *max_element(len.begin(), len.end());
 int nways = 0;
 for(int i = 0; i < len.size(); ++i)
     if(len[i] == maxv) nways += ways[i];
 vector<int> res;
 res.push_back(maxv), res.push_back(nways);
 return res;
}

topCoder: Books

// binary search 
template<typename T1, typename T2> int bsearch(T1 &A, T2 target) {
    int u = 0; 
    int v = A.size()-1;
    while(u < v) {
        int c = (u + v) / 2;
        if (target > A[c]) u=c+1; 
        else v=c;
    }
    return u;
}

// longest non-decreasing sequence 
template<typename T> int lis (vector<T> &seq) {
    if(seq.empty()) return 0;
    vector<T> A;
    int n = seq.size();
    A.push_back(seq[0]);

    int u, v;
    for(int i = 1; i < n; ++i) {
        if(seq[i] >= A.back()) {
            A.push_back(seq[i]);
            continue;
        }
        int u = bsearch(A, seq[i]);
        //important !!! when compute non-increasing or non-decreasing seq
        if(A[u] == seq[i]) A[u+1] = seq[i];
        else A[u] = seq[i];
    }
    return A.size();
}

int Books::sortMoves(vector <string> titles) {
    return books.size()-lis(titles);
}