到达数组末尾的最大得分 Reach End of Array With Max Score

问题 Question

思路 Idea

本题不难想到动态规划

This problem easily leads to thinking about dynamic programming.

class Solution {
    public long findMaximumScore(List<Integer> nums) {
        int n = nums.size();
        long[] dp = new long[n];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int k = 0; k < i; k++) {
                dp[i] = Math.max(dp[i], dp[k] + (long) (i - k) * nums.get(k));
            }
        }
        return dp[n - 1];
    }
}

问题是这里用动态规划时间复杂度为O(N^2)，并且无法用数据结构优化复杂度

The issue is that using dynamic programming here results in a time complexity of O(N^2), and there is no way to optimize the complexity using data structures.

因此这里需要进行脑筋急转弯，注意计算nums[i]*(j-i)相当于对于到i之前的i->j区间用的都是nums[i]累加，那最大的怎么搞？直接用贪心策略选前面最大值即可

Therefore, a brain teaser solution is needed here. Notice that calculating nums[i] * (j - i) is equivalent to using nums[i] for the entire interval from i to j. So how do we find the maximum? Simply use a greedy strategy to select the largest value from the previous elements.

class Solution {
    public long findMaximumScore(List<Integer> nums) {
        long ans = 0;
        long currentMax = 0;
        // 贪心：每次用当前最大值不断累积，直到遇到更大的数值
        // Greedy: Continuously accumulate using the current maximum value
        // until a larger number is encountered.
        for (int num : nums) {
            ans += currentMax;
            currentMax = Math.max(currentMax, num);
        }
        return ans;
    }
}