Java | In-depth Explanation | Easy to Understand
Brute force solution is very easy to come up with. We simply use a nested for-loop to try all the combination so I would skip it. Let\'s think how do we come up
Brute force solution is very easy to come up with. We simply use a nested for-loop to try all the combination so I would skip it. Let\'s think how do we come up with O(n) time solution with one pass?\n  \n  To achieve O(n) time, it\'s obvious we need to use ONE for-loop. Then we need to use variables to track something, right? What should we keep tracking of while we iterate through values[ ]? \n  \n   There are two things we need to track. `max = values[i] + i` and `res` which is the result we wanna return eventually. If we found any greater `max`, we update. If `res` is greater, we also update. That\'s it !\n   \n```\nclass Solution \n{\n    public int maxScoreSightseeingPair(int[] values)\n    {\n        // O(n) time | O(1) space\n        \n        // initialize max and res at the pair (0, 1)\n        int max = values[0] + 0;\n        int res = max + (values[1] - 1);\n        \n        for(int i = 1; i < values.length; i++)\n        {\n            res = Math.max(res, max + values[i] - i);\n            max = Math.max(max, values[i] + i);\n        }\n        return res;\n    }\n}\n```
['Java']