C++ simple different approach O(n) time + O(1) space
\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int ans = 0, prev = values[0];\n        for(int i = 1; i < values.size(); i++){\n            a
```\n    int maxScoreSightseeingPair(vector<int>& values) {\n        int ans = 0, prev = values[0];\n        for(int i = 1; i < values.size(); i++){\n            ans = max(ans, prev - 1 + values[i]);\n            prev = max(values[i], prev - 1);\n        }\n        return ans;\n    }\n```\n\nI haven\'t seen an approach decreasing a current maximum anywhere. So the logic is at each day we decrease the current sum by 1 or pick current day as highest sum. It works because for each day `i` will be equal to `j` and `i - j == 0`.
['Dynamic Programming', 'C', 'C++']