LeetCode: Longest Arithmetic Subsequence of Given Difference Posted on August 5, 2019July 26, 2020 by braindenny Longest Arithmetic Subsequence of Given Difference Similar Problems: LeetCode: Longest Increasing Subsequence CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #dynamicprogramming, #lis Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference. Example 1: Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4]. Example 2: Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element. Example 3: Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1]. Constraints: 1 <= arr.length <= 10^5 -10^4 <= arr[i], difference <= 10^4 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: dp with hashmap: O(N) space + no need for initialization // https://code.dennyzhang.com/longest-arithmetic-subsequence-of-given-difference // Basic Ideas: dynamic programming + hashmap // // dp(i) // j: arr[i]-difference, dp(j)+1 // 1 // Complexity: Time O(n), Space O(n) func longestSubsequence(arr []int, difference int) int { // m[k]: the width when the subsequence ends with k m := map[int]int{} res := 0 for _, v := range arr { // dp[prev] gets 0, if not found m[v] = m[v-difference]+1 // evaluate candidate if m[v] > res { res = m[v] } } return res } Solution: dp with hashmap: O(2N) space // https://code.dennyzhang.com/longest-arithmetic-subsequence-of-given-difference // Basic Ideas: dynamic programming + hashmap // // dp(i) // j: arr[i]-difference, dp(j)+1 // 1 // Complexity: Time O(n), Space O(n) func longestSubsequence(arr []int, difference int) int { m := map[int]int{} dp := make([]int, len(arr)) dp[0] = 1 m[arr[0]] = 0 res := 1 for i:=1; i<len(arr); i++ { prev := arr[i]-difference if j, ok := m[prev]; ok { dp[i] = dp[j]+1 } else { dp[i] = 1 } // update index m[arr[i]] = i // evaluate candidate if dp[i] > res { res = dp[i] } } return res } Post Views: 0 Post navigation LeetCode: Valid Palindrome IIISeries: #lcs – Longest common subsequence & Follow-up Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website