200ms C++ DP solution


  • 3
    G
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int count = 0, n = (int)A.size();
            if (n == 0) return 0;
            unordered_map<long, set<int>> indices;
            for (int i = 0; i < n; ++i)
                indices[(long)A[i]].insert(i);
            vector<vector<int>> counts(n, vector<int>(n, 0));
            for (int j = 1; j < n - 1; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    long prev = (long)A[j] + A[j] - A[k];
                    if (prev < INT_MIN || prev > INT_MAX || !indices.count(prev)) 
                        continue;
                    for (int i : indices[prev]) {
                        if (i >= j) break;
                        counts[j][k] += counts[i][j] + 1;
                    }
                    count += counts[j][k];
                }
            }
            return count;
        }
    };
    

    counts[j][k] is the count of sequences (with lengths greater than 2) ending with indices j and k.
    counts[j][k] = sum{counts[i][j] + 1 | A[i] - A[j] == A[j] - A[k] and i < j}

    Obviously, this solution is not as good as those O(n^2) DP solutions. Any idea why it takes much less time to AC?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.