1937. Maximum Number of Points with Cost

1937. Maximum Number of Points with Cost
mail@pastecode.io avatar
unknown
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