[Java] O(n) Prefix/Suffix sums with a twist
So I had to look at the solution from other people for solving this problem in the discussion section. However, I found the "double maxxing" solution to be real
So I had to look at the solution from other people for solving this problem in the discussion section. However, I found the "double maxxing" solution to be _really_ complicated and difficult to come up with in an interview.\n\nOn one of the posts, I read a nice reformulation of the problem statement: we are interested in finding a pair `(i, j)` where `i < j`, such that:\n\n```text\nA[i] + A[j] + i - j\n```\nis **maximized**.\n\nHowever, this formula can be moved around! Specifically, you can move it around like so: **maximize:**\n```text\n(A[i] + i) + (A[j] - j)\n```\n\nNotice that both these are quantities that are computable over each individual index _without having to depend on other indices_. For example, at index `j = 10` I can compute `A[j] - j` without having to look at any other indices in the array. Now we want to compute the maximum value of this sum of 2 bracketed terms. This _really_ smells like prefix/suffix sums.\n\nThe index `i` has to be _somewhere_ within the array. So we **must** compute the sum `A[i] + i` for each individual index i. However, for one such particular `i`, what `j` to pick? Well, we pick the `j > i` such that `A[j] - j` is maximum.\n\nSo we can solve this problem by keeping an array `P` such that `P[i] = A[i] + i`. We also keep another array `S` such that `S[j] = max(A[j] - j, S[j + 1])`. That is, `S[j] = the maximum value of A[k] - k for all k >= j`.\n\nThen, to get the **maximum** possible value of a sightseeing pair where `i` is fixed, we need to simply look at the sum `P[i] + S[i + 1]`. The maximum value of this sum, is the maximum value overall of any pair!\n\nThe code in Java: \n\n```java\npublic int maxScoreSightseeingPair(int[] A) {  \n        final int n = A.length;\n        \n        int[] P = new int[n];\n        int[] S = new int[n];\n        \n        S[n - 1] = A[n - 1] - (n - 1);\n        \n        // Prepare backward\n        for (int i = n - 2; i >= 0; i--) {\n            S[i] = Math.max(A[i] - i, S[i + 1]);    \n        }\n        \n        // Prepare forward\n        for (int i = 0; i < n; i++) {\n            P[i] = A[i] + i;\n        }\n        \n        int best = Integer.MIN_VALUE;\n        for (int i = 0; i < n - 1; i++) {\n            // For all possible positions of i, \n            // search the best j such that \n            // A[j] - j was the maximum possible\n            // along with A[i] + i itself\n            // S[i + 1] because we cannot double\n            // count index i\n            best = Math.max(best, P[i] + S[i + 1]);\n        }\n        return best;\n    }\n```\n\nHere is a pictorial form of the algorithm:\n\n![image](https://assets.leetcode.com/users/images/e67c0d6d-1b6a-4d38-9433-e2847ea4a668_1610938719.311511.png)\n\n\nHope this helps! This was a tough one for me :)
['Suffix Array']