Leetcode3282. 到达数组末尾的最大得分

Every day a Leetcode

题目来源：3282. 到达数组末尾的最大得分

解法1：动态规划

代码：

class Solution {
public:long long findMaximumScore(vector<int>& nums) {if (nums.size() <= 1) return 0LL;int n = nums.size();vector<long long> dp(n + 1);dp[0] = 0;for (int j = 1; j <= n; j++) {for (int i = 1; i < j; i++) {dp[j] = max(dp[j], dp[i] + 1LL * (j - i) * nums[i - 1]);}}return dp[n];}
};

结果：超时

复杂度分析：

时间复杂度：O(n²)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。

解法2：动态规划 + 贪心

维护一个 maxIndex 表示之前 nums 元素最大值的下标，从贪心的角度思考，从maxIndex 跳到当前下标 i，增加的值最大。

代码：

/** @lc app=leetcode.cn id=3282 lang=cpp** [3282] 到达数组末尾的最大得分*/// @lc code=start
class Solution
{
public:long long findMaximumScore(vector<int> &nums){if (nums.size() <= 1)return 0LL;int n = nums.size();vector<long long> dp(n);dp[0] = 0;int maxIndex = 0;for (int i = 1; i < n; i++){dp[i] = dp[maxIndex] + 1LL * (i - maxIndex) * nums[maxIndex];if (nums[i] > nums[maxIndex])maxIndex = i;}return dp[n - 1];}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。