1027. Longest Arithmetic Subsequence

上来先clarify数的取值范围，然后再决定用哪个

O(n²) time O(n²) space
对于每个A[i]，从前往后枚举之前的每个A[j]，得到一个等差d，利用以A[j]结尾的等差数列长度来更新以A[i]结尾的等差数列的长度

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<unordered_map<int, int>> f(n);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) { // 一定要从前往后，因为是要找最长的，后边的可能更长
                int d = A[i] - A[j];
                f[i][d] = max(2, f[j][d] + 1);
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

O(n²) time O(1001n) space

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<vector<int>> f(n, vector<int>(1001));
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) { // 一定要从前往后，因为是要找最长的，后边的可能更长
                int d = A[i] - A[j] + 500;
                f[i][d] = max(2, f[j][d] + 1);
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

O(500n) time O(500) space
因为题目里每个数都是在0到500之间，所以等差的绝对值肯定是在0到500之间，维护正数等差和负数等差两个数组来记录以x为最后一个数的等差数列的长度，从0到500枚举所有可能的等差，对于每个可能的等差d再枚举数组里的每个数x，看x之前数组里有没有x - d和x + d，用他们的等差数列的长度来更新x的长度，然后再更新全局res

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int pos_step[501], neg_step[501];
        int res = 0;
        for (int d = 0; d <= 500; ++d) {
            memset(pos_step, 0, sizeof(pos_step));
            memset(neg_step, 0, sizeof(neg_step));
            for (int x : A) {
                pos_step[x] = x < d ? 1 : pos_step[x - d] + 1;
                neg_step[x] = x + d > 500 ? 1 : neg_step[x + d] + 1;
                res = max(res, pos_step[x]);
                res = max(res, neg_step[x]);
            }
            if (d > 0 && 501 / d < res) break; // 优化：因为等差d从小到大枚举并更新res，如果当前的等差所能产生的最大长度不足以超过之前的res则没必要继续枚举了，直接返回即可
        }
        return res;
    }
};

O(n²) time O(n²) space
对于等差数列A[i], A[k], A[j]来说，A[i] + A[j] = 2 * A[k]，即对于每个A[j]来说，只要能找到A[i]，即2 * A[k] - A[j]，就找到了一个等差数列
f[i][j]表示以A[i]开始以A[j]结束的等差数列的长度
f[i][j] = f[2 * A[i] - A[j]][i] + 1，即以2 * A[i] - A[j]开始以A[i]结束的等差数列的长度+1，前提是能找到这样的2 * A[i] - A[j]
因为三个数顺序是 2 * A[i] - A[j], A[i], A[j]，所以这道题的计算顺序必须是正向！遍历中间的i，再从i + 1开始遍历j，这样可以保证pos[2 * A[i] - A[j]], i, j的顺序，下面WA的那个遍历j再从j - 1开始遍历i的解法无法确保pos[2 * A[i] - A[j]]和i的顺序

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_map<int, int> pos;
        int res = 2, n = A.size();
        vector<vector<int>> f(n, vector<int>(n, 2));
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int prev = 2 * A[i] - A[j];
                if (pos.count(prev)) {
                    f[i][j] = f[pos[prev]][i] + 1;
                }
                res = max(res, f[i][j]);
            }
            pos[A[i]] = i;
        }
        return res;
    }
};

WA 反例[0,0,0]

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_map<int, int> pos;
        int res = 2, n = A.size();
        vector<vector<int>> f(n, vector<int>(n, 2));
        for (int j = 0; j < n; ++j) {
            f[j][j] = 1;
            for (int i = j - 1; i >= 0; --i) {
                int prev = 2 * A[i] - A[j];
                if (pos.count(prev) && pos[prev] < i) {
                    f[i][j] = f[pos[prev]][i] + 1;
                }
                res = max(res, f[i][j]);
            }
            pos[A[j]] = j;
        }
        return res;
    }
};

O(n²) time O(n²) space
传统思路
对于每个A[i]，遍历其之前的每个A[j]，计算差值d = A[i] - A[j]保存起来
f[i][d]表示以A[i]结尾的差值为d的等差数列的长度
f[i][d] = max{2, f[j][d] + 1} where 0 <= j < i
TLE

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<unordered_map<int, int>> f(n);
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int d = A[i] - A[j];
                f[i][d] = f[i].count(d) ? f[i][d] : max(2, f[j][d] + 1); // 因为是从后往前，后边的可能更长，所以需要判断是否已经用较长的更新过了，否则直接跳过即可
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

TLE

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<unordered_map<int, int>> f(n);
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                int d = A[i] - A[j];
                if (f[i].count(d) == 0) { // 只更新第一次遇到的d再前边的没有更新的意义
                    f[i][d] = max(1, f[j][d]) + 1;
                }
                res = max(res, f[i][d]);
            }
        }
        return res;
    }
};

枚举每个A[i]，再枚举A[i]之后的每个A[j]，得到等差d，用以A[i]结尾以d为等差的等差数列的长度来更新以A[j]结尾以d为等差的等差数列的长度

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int res = 2, n = A.size();
        vector<vector<int>> f(n, vector<int>(1001));
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)  {
                int d = A[j] - A[i] + 500; // 因为每个数都在0到500之间，加一个偏移500把负数等差变成正数
                f[j][d] = max(2, f[i][d] + 1);
                res = max(res, f[j][d]);
            }
        return res;
    }
};

TLE

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<unordered_map<int, int>> f(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int d = A[j] - A[i];
                f[j][d] = f[i].count(d) ? f[i][d] + 1 : 2;
                res = max(res, f[j][d]);
            }
        }
        return res;
    }
};