leetcode每日一题（2020-06-17）：1014. 最佳观光组合

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。

今日学习：
1.动态规划！想到了用动态规划但是没想明白该怎么用！

题解1：

var maxScoreSightseeingPair = function(A) {
    //暴力法[妥妥的超时]
    const res = []
    for(let i = 0; i < A.length; i++) {
        for(let j = i + 1; j < A.length; j++) {
            res.push(A[i] + A[j] + i - j)
        }
    }
    return Math.max(...res)
};

题解2：其实对于每一个 j 来说，A[j] - j 是固定的，所以只需要找到最大的A[i] + i 就是当前 j 的最大结果，换成动态规划的话，就是dp[i]就是 i 之前最大的A[i] + i

// 包括dp[i]和常数个变量【因为和位置无关】
const maxScoreSightseeingPair = (A) => {
    // const dp = new Array(A.length)
    // dp[0] = 0
    let res = prev = 0
    for (let i = 1; i < A.length; i++) {
        // dp[i] = Math.max(dp[i - 1], A[i - 1] + i - 1)
        prev = Math.max(prev, A[i - 1] + i - 1)
        res = Math.max(res, prev + A[i] - i)
    }
    return res
}