BinarySearch 0167 Subsequence Sum

Problem statement

https://binarysearch.com/problems/Subsequence-Sum/

Solution

First, create array arr[i] - i. Then we allowed to take only equal elements from this array. Iterate over them and update d.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        nums2 = [x - i for i, x in enumerate(nums)]
        d = Counter()
        for i, x in enumerate(nums2):
            d[x] += (x + i)

        return max(d.values())