Dynamic Programming

class Solution {
 public:
  int longestArithSeqLength(vector<int>& A) {
    static struct {
      mutable std::optional<int> f[1005][1005];

      void reset(int r, int c) {
        for (int i = 0; i < r; ++i) {
          for (int j = 0; j < c; ++j) {
            f[i][j].reset();
          }
        }
      };
    } mempool;

    const int n = std::size(A);

    auto bottomup_eval_f = [&, f = mempool.f]() {
      for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          const int d = A[i] - A[j] + 500;
          if (f[j][d]) {
            f[i][d] = f[j][d].value() + 1;
          }
          else {
            f[i][d] = 2;
          }
        }
      }
    };

    std::function<int(int, int)> f = [&, memo = (mempool.reset(n, 1005), mempool.f)](int i, int d) {
      if (memo[i][d]) {
        return memo[i][d].value();
      }
      else {
        return memo[i][d].emplace([&] {
          bottomup_eval_f();
          return f(i, d);
        }());
      }
    };


    auto solve = [&](int acc = 0) {
      for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
          acc = std::max(f(i, A[i] - A[j] + 500), acc);
        }
      }
      return acc;
    };

    return solve();
  }
};