Maximum Sum Valid Subsequence - Visa Online Assessment IIT BHU

Problem Preview

"Given an integer array `arr`, select a **subsequence** such that for **every pair of selected elements**, the difference between their values is equal to the difference between their indices. In other words, for any two selected elements at indices `i` and `j`: ```text |arr[i] - arr[j]| = |i - j| ``` Find the **maximum possible sum** of the selected elements. ### Example ```text arr = [1, 5, 4, 3, 7, 8] ``` Suppose we select: ```text 5 at index 1 3 at index 3 ``` Then: ```text Value difference = |5 - 3| = 2 Index difference = |1 - 3| = 2 ``` So these two elements can belong to the same valid subsequence. We need to find the **valid subsequence having the maximum sum**. ### Another Observation For selected indices `i < j`: ```text arr[i] - arr[j] = i - j ``` Rearranging: ```text arr[i] - i = arr[j] - j ``` So, for indices in increasing order, **all selected elements must have the same value of `arr[i] - i`**. ### Output Return the **maximum sum** of a valid subsequence. ### Example ```text Input: arr = [1, 5, 4, 3, 7, 8] ``` For each index: ```text i 0 1 2 3 4 5 arr[i] 1 5 4 3 7 8 arr[i]-i 1 4 2 0 3 3 ``` The group with `arr[i] - i = 3` contains: ```text 7 at index 4 8 at index 5 ``` Their sum is: ```text 7 + 8 = 15 ``` Therefore: ```text Answer = 15 ``` ### Constraints ```text 1 ≤ n ≤ 2 × 10^5 -10^9 ≤ arr[i] ≤ 10^9 ``` **Note:** A single element is also considered a valid subsequence."