# Interesting

• Interesting problem.

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[0]<=...<=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

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