leetcode contest 304 T3

class Solution {
public:
    bool validPartition(vector<int>& ns) {
        int n = ns.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 0;
        dp[2] = ns[0] == ns[1] ? 1 : 0;
        for (int i = 3; i <= n; ++i) {
            if (ns[i - 1] == ns[i - 2] && ns[i - 2] == ns[i - 3]) dp[i] = max(dp[i], dp[i - 3]);
            if (ns[i - 1] == ns[i - 2]) dp[i] = max(dp[i], dp[i - 2]);
            if (ns[i - 1] == ns[i - 2] + 1 && ns[i - 2] == ns[i - 3] + 1) dp[i] = max(dp[i], dp[i - 3]);
        }
        return dp[n] == 1;
    }
};