推 NTUtriangle: 你是leetcode大師 08/17 23:12
→ oin1104: 大師 08/17 23:13
好難喔今天
看答案才知道有這種騷操作== 腦袋不夠好
不過現在leetcode好卡
然後又被overflow搞了一下
我要去漬漬了
long long maxPoints(vector<vector<int>>& points) {
int m = points.size();
int n = points[0].size();
vector<long long> left_max(n,-1);
vector<long long> right_max(n,-1);
vector<long long> dp(n);
for(int i=0; i<n; i++) {
dp[i] = points[0][i];
}
long long ans = *max_element(dp.begin(), dp.end());
for(int i=1; i<m; i++) {
//left_max
left_max[0] = dp[0];
for(int j=1; j<n; j++) {
left_max[j] = max(dp[j], left_max[j-1]-1);
}
//right_max
right_max[n-1] = dp[n-1];
for(int j=n-2; j>=0; j--) {
right_max[j] = max(dp[j], right_max[j+1]-1);
}
//dp
for(int j=0; j<n; j++) {
dp[j] = points[i][j] + max(left_max[j], right_max[j]);
ans = max(ans, dp[j]);
}
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723907467.A.D56.html