技巧 - 下标参与运算时

简介

下标参与val值的计算：

1. 组合评分为：val[i] + val[j] - abs(j - i)

例题

1014. 最佳观光组合

这个题目比较简单：一次遍历，记录每个点作为左观光点时的最大值「mp = max(val[i] + i)」，以当前点均作为右侧观光点「mn[j] = val[j] - j」，更新最值「max(mn[j]+mp)」以及mp

1937. 扣分后的最大得分

解法和上一题有异曲同工之处：

• 第i行，选中某个点j后，考虑左右侧最值
• 因此需要提前处理i-1行分别作为左右时的值；
  • mp[i-1][j]：上一行，该值左侧的最大值
  • mn[i-1][j]：上一行，该值右侧的最大值

    vector<ll> mn(n, 0);
    vector<ll> mp(n, 0);
    mp[0] = dp[i-1][0];
    mn[n-1] = dp[i-1][n-1]-(n-1);
    for (int k = 1; k < n; ++k)
    {
    	mp[k] = max(mp[k-1], dp[i-1][k]+k);
    	mn[n-1-k] = max(mn[n-1-k+1], dp[i-1][n-1-k] - (n-1-k));
    }

• 然后计算当前点作为左/右时的最大值，并更新dp数组

  for (int j = 0; j < n; ++j)
  {
  	dp[i][j] = max(mp[j]+points[i][j]-j, mn[j] + points[i][j]+j);
  	if (i == m - 1) out = max(out, dp[i][j]);
  }

下面这种解法确实更好一些：

class Solution { 
public: long long maxPoints(vector<vector<int>>& points)
{ 
	int m = points.size(), n = points[0].size();
	vector<long long> ret(n), left(n), right(n);
	for (int i = 0; i < m; ++i) { 
		left[0] = ret[0];
		for (int j = 1; j < n; ++j) {
			left[j] = max(ret[j], left[j - 1] - 1);
		} 
		right[n - 1] = ret[n - 1];
		for (int j = n - 2; j >= 0; --j) {
		right[j] = max(ret[j], right[j + 1] - 1);
		} 
		for (int j = 0; j < n; ++j) {
		ret[j] = points[i][j] + max(left[j], right[j]);
		}
	}
	return *max_element(ret.begin(), ret.end());
} };