Longest Arithmetic Subsequence
Updated
Problem statement
You are given an integer array nums. Return the length of its longest arithmetic subsequence.
- A subsequence keeps some of the elements, at least two, in their original order. The kept elements do not have to be next to each other.
- A sequence is arithmetic when the difference between each element and the one before it is always the same. That difference may be positive, zero or negative.
Any two elements form an arithmetic subsequence, so the answer is at least 2.
Function
longestArithmeticSubsequence(nums: int[]) → intExamples
Example 1
nums = [2,9,4,6,13,8,17]return = 4Taking 2, 4, 6, 8 (indices 0, 2, 3, 5) gives a difference of 2 each time, so its length is 4. 9, 13, 17 also works with a difference of 4, but it is shorter. No arithmetic subsequence of length 5 exists, so the answer is 4.
Example 2
nums = [5,31,12,23,9,15,7]return = 4Taking 31, 23, 15, 7 (indices 1, 3, 5, 6) gives a difference of -8 each time. Differences can be negative, so this counts, and its length is 4. No subsequence with a positive or zero difference is longer than 2 here.
Example 3
nums = [4,4,2,4]return = 3The three 4s at indices 0, 1 and 3 form an arithmetic subsequence with difference 0, so the answer is 3.
Constraints
2 <= nums.length <= 10000 <= nums[i] <= 500
More C3.ai interview questions
- Every Result of Grouping an ExpressionONSITE INTERVIEW · Seen Jan 2023
- Fewest Jumps to the Last IndexONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
- Movie Schedule for Maximum EnjoymentONSITE INTERVIEW · Seen Jan 2023
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Can All Courses Be FinishedONSITE INTERVIEW · Seen Nov 2021
- Gas Station LoopONSITE INTERVIEW · Seen Dec 2020
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Maximum Subarray Sum with Equal EndpointsGoogle · ONSITE INTERVIEWGoogle interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
- Word BreakBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions
- Maximum Points by Deleting ElementsWalmart · OAWalmart interview questions
- Predicate Expression Tree EvaluatorMongoDB · PHONE SCREENMongoDB interview questions
- Bitwise XOR SubsequencesJP Morgan Chase · OAJP Morgan Chase interview questions
- Bitwise XOR SubsequencesGoldman Sachs · OAGoldman Sachs interview questions