Recursive->Iterative DP/Greedy||beats 100%
Intuition1st approach tries recursion (with memo). The score can be rewritten by
score=(values[i]+i)+(values[j]-j) for i<j2nd approach is an iterative DP versio
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1st approach tries recursion (with memo). The score can be rewritten by
`score=(values[i]+i)+(values[j]-j)` for `i<j`

2nd approach is an iterative DP version with optimized space. The interesting thing is that the 2nd solution can be interpreted also as a Greedy algorithm.(P.S. How about Kadane's Algorithm?)

3rd approach is using std::accumulate with lambda which is also fast.
# Approach
<!-- Describe your approach to solving the problem. -->
[Please Turn on English subtitles if necessary]
[https://youtu.be/-15Q6Zc_piI?si=noYrDlAKtOxHxhkk](https://youtu.be/-15Q6Zc_piI?si=noYrDlAKtOxHxhkk)
1. Use C-array to declare state array `dp` as a global variable to store `dp[i]=max(values[k]+k for k<=i)`
2. Let `score` be a member variable
3. Define the recursive function `int f(int i, vector<int>& values)` compute `score=max(score, dp[i-1]+(values[i]-i))` & `dp[i]`.
4. In `maxScoreSightseeingPair` fill `dp` with `0`
5. Apply `f(n-1, values)`
6. `score` is the answer
7. 2nd approach is an iterative DP version with optimized space. The state array `dp` can be reduced to 1 single variable.
8.  Recheck the 1st appoach, it's found there is no need for memoization to avoid of redudant computing( because the recursion has only 2 terms, current & previous). A pure recursion suffices to obtain a 0ms code.
9.  C++ STL accumulate is the 3rd approach.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)\to O(1)$
# Code Recursion (with Memo)||both of C++ 0ms beat 100%
```cpp [Recursive C++]
class Solution {
public:
    int score=0;
    int f(int i, vector<int>& values){
        if (i<0) return 0;
    
        int x=values[i], prev=f(i-1, values);
        score=max(score, prev+x-i);
        return max(prev, x+i);
    }
    int maxScoreSightseeingPair(vector<int>& values) {
        const int n=values.size();

        f(n-1, values);
        return score;
    }
};
```
```cpp [C++  recursion with memo]
int dp[50000];// for max i
class Solution {
public:
    int score=0;
    int f(int i, vector<int>& values){
        if (i<0) return 0;
        if(dp[i]!=0) return dp[i];
        int x=values[i], prev=f(i-1, values);
        score=max(score, prev+x-i);
        return dp[i]=max(prev, x+i);
    }
    int maxScoreSightseeingPair(vector<int>& values) {
        const int n=values.size();
        fill(dp, dp+n, 0);
        f(n-1, values);
        return score;
    }
};
```
# Iterative DP/Greedy||C++ 0ms
```C++ []
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        const int n=values.size();
        if (n==2) return values[0]+values[1]-1;
        int dp=values[0], score=0;
        for(int i=1; i<n; i++){
            int x=values[i];
            score=max(score, dp+x-i);
            dp=max(dp, x+i);
        }
        return score;
    }
};
```
```Python []
class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        n=len(values)
        dp, score=0, 0
        for i, x in enumerate(values):
            score=max(score, dp+x-i)
            dp=max(dp, x+i)
        return score
        
```
# C++ using accumulate||0ms
```
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        return accumulate(values.begin(), values.end(), 0, 
        [dp=0, i=0](int score, int x) mutable{
            score=max(score, dp+x-i);
            dp=max(dp, x+i++);
            return score;
        });
    }
};
```
# The DP/Greedy solutions are similar to Kadane's algorithm
Kadane's algorithm is used for solving some other problems which are more as follows:
[121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solutions/3758901/c-python-greedy-explain-w-pyplot/)

[918. Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/solutions/3722855/w-explanationc-using-kadanes-algorithm/)

[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-interview-150)

[152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/solutions/3748707/c-kadane-s-algorithm/)

[2272. Substring With Largest Variance](https://leetcode.com/problems/substring-with-largest-variance/solutions/3738775/c-kadane-s-algorithm/)
['Array', 'Dynamic Programming', 'Greedy', 'Memoization', 'C++', 'Python3']