Leetcode – Medium – DP – Non Decreasing Array

Home   »   Leetcode – Medium – DP – Non Decreasing Array

class Solution {
    
    int n;
    vector> dp;
    
    bool f(int i, int canTake, vector> &dp, vector &nums){
        if(i>=n) return dp[i][canTake] = true;
        bool flag = true;
        if(i-1>=0) if(!(nums[i-1]<=nums[i])) flag = false;
        bool check = false;
        if(canTake){
            if(flag) check = check || f(i+1,canTake,dp,nums);
            int cur = nums[i];
            nums[i] = nums[i-1];
            check = check || f(i+1,0,dp,nums);
            nums[i] = cur;
            return dp[i][canTake] = check;
        }
        else {
            if(flag) return dp[i][canTake] = f(i+1,0,dp,nums);
            else return dp[i][canTake] = false;
        }
    }
    
public:
    bool checkPossibility(vector& nums) {
        n = nums.size();
        
        dp = vector> (n+2,vector(2,-1));
        
        bool ans = f(1,1,dp,nums);
        
        if(ans) return true;
        if(n>=2){
            if(nums[1]> (n+2,vector(2,-1));
                nums[0] = nums[1];
                ans = f(1,0,dp,nums);
            }
            return ans;
        }
        return false;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *