Java Dynamic Programming with explanation and example
Approach\n Describe your approach to solving the problem. \nDynamic Programming\n# Complexity\n- Time complexity:O(N)\n Add your time complexity here, e.g. O(n)
# Approach\n<!-- Describe your approach to solving the problem. -->\nDynamic Programming\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maxScoreSightseeingPair(int[] A) {\n        // A[i] + A[j] + i - j = (A[i]+i) + (A[j]-j)\n        // think about dividing them into two parts\n        // get the max of left part and right part, then add them \n        // to get the maximum score\n        //\n        //                 max(left)   + max(right)\n        // maximum score = max(A[i]+i) + max((A[j]-j))\n\n        /* example:\n          i  0  1  2  3  4\n          A [8, 1, 5, 2, 6], max = 0\n          \n            i=1,\n                left  = A[0]+0 = 8\n                right = A[1]-1 = 0\n                => max = max(max=0, left + right=8)    = 8\n                Before moving to i=2, we need to update left part by \n                comparing current left and right\n                so ----> left = max(left=8, A[1]+1=2)  = 8\n            i=2,\n                left  = 8\n                right = A[2]-2 = 3\n                => max = max(max=8, left + right=11)   = 11\n                so ----> left = max(left=8, A[2]+2=7)  = 8 \n            i=3,\n                left  = 8\n                right = A[3]-3 = 1\n                => max = max(max=11, left + right=9)   = 11\n                so ----> left = max(left=8, A[3]+3=5)  = 8 \n            i=4,\n                left  = 8\n                right = A[4]-4 = 2\n                => max = max(max=11, left + right=10)  = 11\n                so ----> left = max(left=8, A[4]+4=10) = 8            \n            end loop\n                max = 11\n        */\n        int N = A.length;\n        int left = A[0]+0;\n        int right = 0; \n        int max = 0;\n\n        for (int i=1; i<N; i++){\n            right = A[i]-i;\n            max = Math.max(max, left+right);\n            // before we move on, we need to update the state of left part\n            // now our current right part will become left part in next round\n            left = Math.max(left, A[i]+i); \n        }\n        return max;\n    }\n}\n```
['Java']