DP optimization
IntuitionApproachwrite brute force ->tabulation->draw diagrams->observe something->optimise
general flow for any dp optimizationsComplexity
Time complexity:

Sp
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
write brute force ->tabulation->draw diagrams->observe something->optimise
general flow for any dp optimizations
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        N = len(nums)
        dd = 301
        d =defaultdict(list)
        for i,x in enumerate(nums):d[x].append(i)
        dp = [[1] * dd for _ in range(N)] 
        idx = [-1]*(dd)
        idx[nums[-1]]  = N-1
        for i in range(N - 2, -1, -1):
            mx = 0
            for prev in range(dd):
                if nums[i] - prev>=0 and idx[nums[i]-prev]!=-1:
                    f = idx[nums[i]-prev]
                    mx = max(dp[f][prev],mx)
                if nums[i] + prev < dd and idx[nums[i] + prev]!=-1:
                    f = idx[nums[i] + prev]
                    mx = max(dp[f][prev],mx)
                #brute force
                # ans = 1
                # for j in range(prev + 1):
                #     ele1 = nums[i] - j
                #     ele2 = nums[i] + j
                #     if ele1 in d:
                #         jj = bisect_right(d[ele1], i)
                #         if jj != len(d[ele1]):
                #             jjj = d[ele1][jj]
                #             ans = max(ans, 1 + dp[jjj][j])
                #     if ele2 in d:
                #         jj = bisect_right(d[ele2], i)
                #         if jj != len(d[ele2]):
                #             jjj = d[ele2][jj]
                #             ans = max(ans, 1 + dp[jjj][j])
                dp[i][prev] = max(dp[i][prev],mx + 1)

            idx[nums[i]] = i
        result = max(max(dp[i]) for i in range(N))

        return result

```
['Python3']