1937. Maximum Number of Points with Cost
1937. Maximum Number of Points with Costunknown
c_cpp
a month ago
1.1 kB
2
Indexable
Never
class Solution { public: long long maxPoints(vector<vector<int>>& points) { int n = (int)points.size(), m = (int) points.front().size(); long long prvMax, curMax = INT_MIN; vector<vector<long long>> dp(2,vector<long long>(m,0LL)); for(int i = 0; i < m; ++i) { dp[0][i]= (long long)points[0][i]; } int index = 1; for(int i = 1; i < n; ++i) { prvMax = INT_MIN; curMax = INT_MIN; for(int j = 0; j < m; ++j) { prvMax = max(prvMax-1, dp[index^1][j]); dp[index][j] = max(prvMax+points[i][j], dp[index][j]); } prvMax = INT_MIN; curMax = INT_MIN; for(int j = m-1; j >= 0; --j) { prvMax = max(prvMax-1, dp[index^1][j]); dp[index][j] = max(prvMax+points[i][j], dp[index][j]); } index ^= 1; } auto ans = max_element(dp[index^1].begin(), dp[index^1].end()); return *ans; } };
Leave a Comment