🔥🚀 Kotlin/Java O(n) time & O(1) space easy solution
Approach\nThe hint is to compute best first pairing for index i (at i > 0) at each run and then sum it up with current value, the maximum of these summaries is 
# Approach\nThe hint is to compute best first pairing for index i (at i > 0) at each run and then sum it up with current value, the maximum of these summaries is the answer.\n\nSo basically:\n\n1. set current optimal to values[0]\n2. at index i -> find out if it is more suitable to reuse previous currentOptimal (decremented, because it is 1 more index further) or to use previous value. This gives us optimal choice for first sigthseeing in pair. \n3. Then sum up currentOptimal + values[i]\n4. If it is larger than max, assign to max\n5. return max\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n```kotlin []\nclass Solution {\n    fun maxScoreSightseeingPair(values: IntArray): Int {\n        var max = Int.MIN_VALUE\n        var currentOptimal = values[0]\n\n        for (i in 1 until values.size) {\n            currentOptimal = maxOf(currentOptimal-1, values[i-1]-1)\n            max = maxOf(max, currentOptimal+values[i])\n        }\n        return max\n    }\n}\n```\n```java []\nclass Solution {\n    public int maxScoreSightseeingPair(int[] values) {\n        int n = values.length;\n        int max = Integer.MIN_VALUE;\n        int currentOptimal = values[0];\n\n        for (int i = 1; i < n; i++) {\n            currentOptimal = Math.max(currentOptimal-1, values[i-1]-1);\n            max = Math.max(max, currentOptimal + values[i]);\n        }\n\n        return max;\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Java', 'Kotlin']