刷题笔记合集🔗

分割数组的最大差值

问题描述

给定一个由若干整数组成的数组 ，可以在数组内的任意位置进行分割，将该数组分割成两个非空子数组（即左数组和右数组），分别对子数组求和得到两个值，计算这两个值的差值，请输出所有分割方案中，差值最大的值。

输入格式

第一行输入数组中元素个数 ，。
第二行输入数字序列，以空格进行分隔，数字取值为 4 字节整数。

输出格式

输出差值的最大取值。

样例输入

6
1 -2 3 4 -9 7

样例输出

10

数据范围

• 
• 数组元素为 4 字节整数

题解

这道题要求在数组的任意位置分割，形成两个非空子数组，然后求它们和的差值的最大值。

解决这个问题的关键是了解如何高效计算每个分割点的差值。一个直观的思路是枚举所有可能的分割点，计算左右子数组的和，取差值的最大值。

由于需要遍历所有分割点，时间复杂度至少是O(n)。但如果每次都重新计算左右子数组的和，时间复杂度会增加到O(n²)，这对于n最大为100000的情况可能会超时。

更高效的方法是提前计算整个数组的总和sum，然后从左到右遍历数组，维护一个变量leftSum表示当前左子数组的和。对于每个分割点i，右子数组的和就是rightSum = sum - leftSum。差值就是|leftSum - rightSum|。

算法步骤：

1. 计算整个数组的总和sum
2. 初始化leftSum = 0, maxDiff = 0
3. 遍历数组的前n-1个元素（因为右子数组至少要有一个元素）
4. 对于每个元素i：
   • 更新leftSum += nums[i]
   • 计算rightSum = sum - leftSum
   • 计算差值diff = |leftSum - rightSum|
   • 更新maxDiff = max(maxDiff, diff)
5. 返回maxDiff

这个算法的时间复杂度是O(n)，空间复杂度是O(1)，对于给定的数据范围是完全可行的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
nums = list(map(int, input().split()))

# 查找最大差值
def find_max_diff(arr):
    """计算分割数组可得到的最大差值"""
    # 计算整个数组的总和
    total = sum(arr)
    
    left_sum = 0
    max_diff = 0
    
    # 遍历前n-1个元素(最后一个元素必须在右侧子数组)
    for i in range(len(arr) - 1):