Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.
In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].
If there is no way to make arr1 strictly increasing, return -1.
Keyword: DP
New method used here: bisect.bisect_right to find an index for value in a sorted array
Solution:
import bisect
class Solution(object):
def makeArrayIncreasing(self, arr1, arr2):
"""
:type arr1: List[int]
:type arr2: List[int]
:rtype: int
"""
if len(arr1) <= 1: return 0
arr2.sort()
record = {} # (value, number of operations to get this value)
record[-1] = 0
for number in arr1:
# record is what we get for each possible value before this position
# for each number i at this position, we try two paths:
# if it's larger then record[i] => (record[i], number of operations)
# else then try to find other keys in record to make it work
temp = {}
for key in record.keys():
if key < number:
temp[number] = min(temp.get(number, 999999), record[key])
leastOptionPos = bisect.bisect_right(arr2, key)
# first iteration, it will find minimal value in arr2
# to be another option to replace in first position
if leastOptionPos < len(arr2):
replaceNumber = arr2[leastOptionPos]
temp[replaceNumber] = min(temp.get(replaceNumber, 999999), record[key] + 1) # replace
record = temp
print record
if record:
return min(record.values())
return -1Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.
Note that the subarray needs to be non-empty after deleting one element.
Keyword: DP
Idea: find maxSubarrayEndHere and maxSubarrayStartHere for each position, then we find max value result for each position’s maxSubarrayEndHere[i-1] + maxSubarrayStartHere[i+1]