Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 23

Description

Longest Arithmetic Subsequence

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

• A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
• A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation:  The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation:  The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:  The longest arithmetic subsequence is [20,15,10,5].

Constraints:

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

Solution

class Solution {
public:
  int longestArithSeqLength(vector<int>& nums) {
    int len = nums.size();
    if(len < 2) return len;

    int dp[len + 1][1001];
    memset(dp, 0, sizeof(dp));
    int answer = 1;
    for(int i = 1; i < len; ++i) {
      for(int j = 0; j < i; ++j) {
        int diff = nums[j] - nums[i] + 500;
        int count = 1;

        if(dp[j][diff]) {
          count = dp[j][diff];
        }

        dp[i][diff] = 1 + count;
        answer = max(answer, dp[i][diff]);
      }
    }

    return answer;
  }
};

// Accepted
// 63/63 cases passed (148 ms)
// Your runtime beats 96.32 % of cpp submissions
// Your memory usage beats 93.59 % of cpp submissions (13.9 MB)