刷题笔记合集🔗

问题描述

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

输入格式

第一行输入数组中元素个数n,1<n≤100000。

第二行输入数字序列,以空格分隔,数字取值为4字节整数。

输出格式

输出差值的最大取值。

样例1

输入:

6
1 -2 3 4 -9 7

输出:

10

说明:

• 可行的分割方案有:
  1. [1] 和 [-2,3,4,-9,7], 差值=|1-3|=2
  2. [1,-2] 和 [3,4,-9,7], 差值=|-1-5|=6
  3. [1,-2,3] 和 [4,-9,7], 差值=|2-2|=0
  4. [1,-2,3,4] 和 [-9,7], 差值=|6-(-2)|=8
  5. [1,-2,3,4,-9] 和 [7], 差值=|-3-7|=10
• 最大的差值为10

题解

本题可以使用前缀和法解决:

1. 计算整个数组的和sum
2. 从左到右遍历:
   • 左边的和leftSum不断增加
   • 右边的和rightSum=sum-leftSum
   • 计算差值|leftSum-rightSum|
   • 更新最大差值
3. 遍历到倒数第二个数为止

时间复杂度:O(n),其中n为数组长度。

参考代码

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

def getResult():
    left_sum = 0
    right_sum = sum(nums)
    max_diff = 0
    
    for i in range(n-1):
        left_sum += nums[i]
        right_sum -= nums[i]
        diff = abs(left_sum - right_sum)
        max_diff = max(max_diff, diff)
    
    return max_diff

print(getResult())

import j