The problem basically ask whether it possible to modify a value to make a given array non-strictly increasing(including equality).
Brute force search for the problem is to check every combination (p,v) of the modifying position p and the value v after modification. Because v have a large range. Search method is not applicable.
Notice there are strong constraints on the replaced value, which is to make nums<=...<=nums[i-1]<=nums[i]<=nums[i+1]<=....<=nums[n-1] holds.
We can have a dynamic programming algorithm to solve the problem. Because if nums[0:n] is non-decreasing, nums[0:i] must also be non-decreasing. So the sub-problem become the minimum modifying to make nums[0:i] non-decreasing.
If nums[i]<nums[i+1], no modifying work is needed to expand solution from i to i+1.
If nums[i]>nums[i+1], we got two options to expand our solution.One is to lower the nums[i], the other is to raise the nums[i+1]. The range to decrease nums[i] depends on whether nums[i-1]<=nums[i] still holds.
Here comes the greedy solution. Since the modified value is under strong constraint, we should do minimum modifying to best preserve the order relation. so let nums[i] = num[i+1] when to do the minimum decreasing, when that don't break the original nums[0:i] solution. Or just increasing nums[i+1] to expand solution to nums[0:i+1].
/The greedy proofs to be done./
class Solution(object): def checkPossibility(self, nums): """ :type nums: List[int] :rtype: bool """ mi = min(nums) nums = [mi]+nums cnt = 0 for i in range(1,len(nums)-1): if nums[i]>nums[i+1]: if nums[i-1]<=nums[i+1]: nums[i]=nums[i+1] cnt += 1 else: nums[i+1]=nums[i] cnt += 1 return cnt<=1