这个题解使用了一种非常特殊的方法,从数组末端开始,并尽可能地将相邻的满足条件的数合并,从而使得数组尽可能的缩减。它利用了一个重复的过程,通过不断检查并合并满足 nums[i] <= nums[i+1] 条件的相邻元素对,然后删除前者,这样不断重复,直到不能再合并为止。当数组长度减少到20以下时,程序会进一步加速处理。另外,这个解还采用了动态分段和调整段大小的策略,以尝试优化处理速度和合并效果。
时间复杂度: O(n^2)
空间复杂度: O(n)
def maysum(l, maxnum):
# 计算给定列表的和,如果大于已知最大值,则保持不变,否则合并为一个元素
result = sum(l)
if result > maxnum:
return l
return [result]
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
index = len(nums) - 1
d = index - 300
kp, k, score = 128, 2, 10
wuhu = nums.pop
while index - 1 >= 0:
if nums[index] >= nums[index-1]: nums[index-1] += nums[index]
index -= 1
wuhu()
if index < 20:
while index - 1 >= 0:
if nums[index] >= nums[index-1]: nums[index-1] += nums[index]
index -= 1
wuhu()
break
if index < d:
slice_nums = (nums[i:i+kp:] for i in range(0, index+1, kp))
nums = [item for items in map(lambda slice_nums: maysum(slice_nums, nums[index]), slice_nums) for item in items]
record = index
index = len(nums) - 1
wuhu = nums.pop
recordscore = score
score = record - index
if score > recordscore:
k *= 8
else:
k = 1/k
result = int(kp*k) // 8
if result > 1: kp = result
d_ = index - index // 50 if index > 200 else index - 20
if d_ > 0: d = d_
return nums[0]