最大化剩余最后三个元素的和：最优解法问询

问题分析 #

每次删除相邻两个元素，最终剩余3个元素。由于初始数组长度n为奇数，每次操作后长度仍为奇数，最终剩余3个元素的位置需满足：中间元素与前后两个元素的索引奇偶性不同（即前、后元素索引奇偶性相同，中间元素相反）。这是因为两个保留元素之间的元素个数必须为偶数，才能通过成对删除清空。

核心思路 #

遍历每个可能作为中间元素的位置j（1 ≤ j ≤ n-2，索引从0开始），计算以下两类情况的最大和：

• 若j是奇数：寻找j左侧最大的偶索引元素值 + a[j] + j右侧最大的偶索引元素值
• 若j是偶数：寻找j左侧最大的奇索引元素值 + a[j] + j右侧最大的奇索引元素值

最终取所有情况的最大值即为答案。

具体实现步骤 #

1. 预处理左右侧的最大奇偶索引值 #

我们可以用数组存储遍历过程中遇到的最大偶索引元素和最大奇索引元素，也可以用变量优化空间复杂度至O(1)：

• 左侧预处理：从左到右遍历，记录到每个位置j左侧的最大偶、奇索引元素值
• 右侧预处理：从右到左遍历，记录到每个位置j右侧的最大偶、奇索引元素值

2. 遍历计算最大和 #

遍历每个中间位置j，根据j的奇偶性，结合预处理得到的左右侧最大值计算当前和，更新全局最大值。

代码示例（Python） #

def max_remaining_sum(arr):
    n = len(arr)
    if n == 3:
        return sum(arr)
    
    # 预处理左侧最大偶、奇索引值
    left_max_even = [-float('inf')] * n
    left_max_odd = [-float('inf')] * n
    curr_max_even = -float('inf')
    curr_max_odd = -float('inf')
    for j in range(1, n):
        prev_idx = j - 1
        if prev_idx % 2 == 0:
            curr_max_even = max(curr_max_even, arr[prev_idx])
        else:
            curr_max_odd = max(curr_max_odd, arr[prev_idx])
        left_max_even[j] = curr_max_even
        left_max_odd[j] = curr_max_odd
    
    # 预处理右侧最大偶、奇索引值
    right_max_even = [-float('inf')] * n
    right_max_odd = [-float('inf')] * n
    curr_max_even = -float('inf')
    curr_max_odd = -float('inf')
    for j in range(n-2, -1, -1):
        next_idx = j + 1
        if next_idx % 2 == 0:
            curr_max_even = max(curr_max_even, arr[next_idx])
        else:
            curr_max_odd = max(curr_max_odd, arr[next_idx])
        right_max_even[j] = curr_max_even
        right_max_odd[j] = curr_max_odd
    
    max_sum = -float('inf')
    for j in range(1, n-1):
        if j % 2 == 1:
            # 中间是奇数，取左右偶索引最大值
            current_sum = left_max_even[j] + arr[j] + right_max_even[j]
        else:
            # 中间是偶数，取左右奇索引最大值
            current_sum = left_max_odd[j] + arr[j] + right_max_odd[j]
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum

复杂度分析 #

• 时间复杂度：O(n)，仅需三次线性遍历（左侧预处理、右侧预处理、遍历中间元素）
• 空间复杂度：O(n)，若要优化为O(1)，可在遍历中间元素时同步计算右侧最大值，或使用变量替代数组存储预处理结果。

内容的提问来源于stack exchange，提问作者20BCS029-Ishtiyak Ahmad Khan