C++_O(n) _Dynamic Programming


  • 1
    class Solution {
    public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if(timeSeries.empty()) return 0;
        int n = timeSeries.size();
        vector<int> dp(n, 0);
        int res = 0;
        int start = timeSeries[0];
        dp[0] = timeSeries[0] + duration;
        for(int i = 1; i < n; ++i){
            if(dp[i-1] < timeSeries[i]){
                res += dp[i-1] - start;
                start = timeSeries[i];
                dp[i] = timeSeries[i] + duration;
            }else{
                dp[i] = max(dp[i-1], timeSeries[i] + duration);
            }
        }
        res += dp[n-1] - start;
        return res;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.