Longest AP

mail@pastecode.io avatarunknown
c_cpp
2 months ago
509 B
7
Indexable
Never
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        //sort the array before
        vector<vector<int>> dp(nums.size(), vector<int>(1001, 1));
        int mx = 1;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j] + 500;
                dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1);
                mx = max(dp[i][diff], mx);
            }
        }
        return mx;
    }
};