In this guide, you will get 1027. Longest Arithmetic Subsequence LeetCode Solution with the best time and space complexity. The solution to Longest Arithmetic Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
1027. Longest Arithmetic Subsequence LeetCode Solution in C++
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
// dp[i][k] := the length of the longest arithmetic subsequence of
// nums[0..i] with k = diff + 500
vector<vector<int>> dp(n, vector<int>(1001));
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j) {
const int k = nums[i] - nums[j] + 500;
dp[i][k] = max(2, dp[j][k] + 1);
ans = max(ans, dp[i][k]);
}
return ans;
}
}; /* code provided by PROGIEZ */
1027. Longest Arithmetic Subsequence LeetCode Solution in Java
class Solution {
public int longestArithSeqLength(int[] nums) {
final int n = nums.length;
int ans = 0;
// dp[i][k] := the length of the longest arithmetic subsequence of nums[0..i]
// with k = diff + 500
int[][] dp = new int[n][1001];
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j) {
final int k = nums[i] - nums[j] + 500;
dp[i][k] = Math.max(2, dp[j][k] + 1);
ans = Math.max(ans, dp[i][k]);
}
return ans;
}
} // code provided by PROGIEZ
1027. Longest Arithmetic Subsequence LeetCode Solution in Python
class Solution:
def longestArithSeqLength(self, nums: list[int]) -> int:
n = len(nums)
ans = 0
# dp[i][k] := the length of the longest arithmetic subsequence of nums[0..i]
# with k = diff + 500
dp = [[0] * 1001 for _ in range(n)]
for i in range(n):
for j in range(i):
k = nums[i] - nums[j] + 500
dp[i][k] = max(2, dp[j][k] + 1)
ans = max(ans, dp[i][k])
return ans # code by PROGIEZ
