DP练习（初级）：ZigZag

题目来源：http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

类似于求最长子串的方法。dp[0][i]表示以 元素sequence[i] 结尾的且它比子串中前一个数小的 最大子串，dp[1][i] 表示以 元素sequence[i] 结尾的且它比子串中前一个数大的 最大子串。

代码如下：

#include <algorithm>#include <iostream>#include <sstream>#include <string>#include <vector>#include <stack>#include <deque>#include <queue>#include <set>#include <map>#include <cstdio>#include <cstdlib>#include <cctype>#include <cmath>#include <cstring>using namespace std;/*************** Program Begin **********************/int dp[2][50];class ZigZag {public:    int longestZigZag(vector <int> sequence) {        int res = 1;int N = sequence.size();dp[0][0] = dp[1][0] = 1;for (int i = 1; i < N; i++) {dp[0][i] = dp[1][i] = 1;for (int j = 0; j < i; j++) {if (sequence[i] > sequence[j]) {if (dp[1][i] < dp[0][j] + 1) {dp[1][i] = dp[0][j] + 1;}} else if (sequence[i] < sequence[j]) {if (dp[0][i] < dp[1][j] + 1) {dp[0][i] = dp[1][j] + 1;}}}res = max(res, dp[0][i]);res = max(res, dp[1][i]);}        return res;    }};/************** Program End ************************/