Best Sightseeing Pair LeetCode solution in Java

1
class Solution {
2
  public int maxScoreSightseeingPair(int[] A) {
3
    // A[i] + A[j] + i - j = (A[i]+i) + (A[j]-j)
4
    // think about dividing them into two parts
5
    // get the max of left part and right part, then add them
6
    // to get the maximum score
7
    //
8
    //                 max(left)   + max(right)
9
    // maximum score = max(A[i]+i) + max((A[j]-j))
10

11
    /* example:
12
      i  0  1  2  3  4
13
      A [8, 1, 5, 2, 6], max = 0
14

15
        i=1,
16
            left  = A[0]+0 = 8
17
            right = A[1]-1 = 0
18
            => max = max(max=0, left + right=8)    = 8
19
            Before moving to i=2, we need to update left part by
20
            comparing current left and right
21
            so ----> left = max(left=8, A[1]+1=2)  = 8
22
        i=2,
23
            left  = 8
24
            right = A[2]-2 = 3
25
            => max = max(max=8, left + right=11)   = 11
26
            so ----> left = max(left=8, A[2]+2=7)  = 8
27
        i=3,
28
            left  = 8
29
            right = A[3]-3 = 1
30
            => max = max(max=11, left + right=9)   = 11
31
            so ----> left = max(left=8, A[3]+3=5)  = 8
32
        i=4,
33
            left  = 8
34
            right = A[4]-4 = 2
35
            => max = max(max=11, left + right=10)  = 11
36
            so ----> left = max(left=8, A[4]+4=10) = 8
37
        end loop
38
            max = 11
39
    */
40
    int N = A.length;
41
    int left = A[0] + 0;
42
    int right = 0;
43
    int max = 0;
44

45
    for (int i = 1; i < N; i++) {
46
      right = A[i] - i;
47
      max = Math.max(max, left + right);
48
      // before we move on, we need to update the state of left part
49
      // now our current right part will become left part in next round
50
      left = Math.max(left, A[i] + i);
51
    }
52
    return max;
53
  }
54
}