合并后数组中的最大元素

标签: 贪心 数组

难度: Medium

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

  • 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Submission

运行时间: 60 ms

内存: 29.8 MB

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)) # 根据kp划区
                nums = [item for items in map(lambda slice_nums:maysum(slice_nums,nums[index]),slice_nums) for item in items]
                # 根据合并数据调整比例
                record = index                      # 记录index
                index = len(nums) - 1               # 更新合并后的index
                wuhu = nums.pop
                recordscore = score                 # 记录上次分数
                score = record - index              # 生成新分数
                # print(f"kp:{kp},k:{k},len:{index}",end="")  
                # 根据分数判断情况
                if score > recordscore:
                    # 比例放大
                    k*=8
                else:
                    # 比例缩小并反转
                    k=1/k
                result = int(kp*k)//8
                if result > 1:kp = result
                # print(f"kp:{kp},k:{k}，score:{score}")    
                d_ = index - index//50 if index > 200 else index - 20
                if d_ > 0:d = d_
                    
        return nums[0]

Explain

这个题解使用了一种非常特殊的方法，从数组末端开始，并尽可能地将相邻的满足条件的数合并，从而使得数组尽可能的缩减。它利用了一个重复的过程，通过不断检查并合并满足 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]

Explore

在题解中，动态分段和调整段大小的策略是通过改变变量`kp`的值来实现的。这个变量代表每个分段包含的元素数量。初始时`kp`设为128，根据数组的处理进度，如果`score`（当前步骤减少的数组长度与前一步骤相比）增加，说明更大的段大小可能更有效，因此将`k`（一个影响`kp`的因子）增加8倍；如果`score`减少，`k`则被设为其倒数，从而减小段大小。调整`kp`的值是通过`kp = int(kp * k) // 8`实现的。这种策略的目的是让算法能够根据当前数据的特性动态调整处理的粒度，理论上能够在不同的数据集和处理阶段优化性能，提高算法的效率和响应速度。

在题解中，`wuhu = nums.pop`实际上是将`nums.pop`方法赋给了变量`wuhu`，这是一种简化代码的做法。然而，从代码的上下文来看，虽然`wuhu()`被调用了，但这种调用方式并未直接体现其作用，因为没有对`wuhu`的调用结果进行处理或使用。这可能是代码实现过程中的一个误用或者是为了某种未明确的副作用（例如可能原意是用来调试或检测）。如果没有具体的副作用或目的，这种做法可能会引起一些混淆或是不必要的性能开销。

在题解中，选择20作为处理策略改变的阈值可能基于以下考虑：当数组长度显著减小，处理每个元素的相对开销变大，因此采用更直接的方法处理小数组可能更有效。直接合并相邻满足条件的元素在小数组中操作更快，因为小规模数据上的迭代操作相对较快，且管理和维护的开销较小。此策略可以减少在小数组上不必要的复杂操作，提高算法的总体效率，尤其是在接近最终结果时。