E卷-刷题笔记合集🔗

分割数组的最大差值

问题描述

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

输入格式

第一行输入一个正整数 ，表示数组中元素的个数，其中 。

第二行输入 个整数，以空格分隔，表示数组 中的元素，每个数字的取值范围为 4 字节整数。

输出格式

输出一个整数，表示所有分割方案中，左右子数组和的差值的最大值。

样例输入1

6
1 -2 3 4 -9 7

样例输出1

10

样例解释

样例 解释说明

样例1	将数组 nums 划分为两个非空数组的可行方案有： 左数组 = 且 右数组 = [-2,3,4,-9,7]，和的差值 = | 1 - 3 | = 2 左数组 = [1,-2] 且 右数组 = [3,4,-9,7]，和的差值 = | -1 - 5 | = 6 左数组 = [1,-2,3] 且 右数组 = [4,-9,7]，和的差值 = | 2 - 2 | = 0 左数组 = [1,-2,3,4] 且 右数组 = [-9,7]，和的差值 = | 6 - (-2) | = 8 左数组 = [1,-2,3,4,-9] 且 右数组 = ，和的差值 = | -3 - 7 | = 10 最大的差值为 10

数据范围

• 
• 数组中的每个元素都是 4 字节整数

题解

枚举

这道题目要求在数组中找到一个分割点，使得左右两部分的和的差值最大。解决这个问题的关键在于理解如何高效地计算所有可能的分割方案。

一个直观的思路是：

1. 先计算整个数组的总和。
2. 然后从左到右遍历数组，每次将当前元素从右边和中减去，加入左边和中。
3. 计算每次分割后左右两部分的差值，并更新最大差值。

这个方法之所以高效，是因为它只需要遍历数组一次就能得到所有可能的分割方案的差值。

具体步骤如下：

1. 计算数组 nums 的总和 total_sum。
2. 初始化左边和 left_sum 为 0，右边和 right_sum 为 total_sum。
3. 初始化最大差值 max_diff 为负无穷大。
4. 遍历数组 nums，对于每个元素 num（除了最后一个）：
   • 将 num 从 right_sum 中减去，加入 left_sum。
   • 计算当前左右和的差值的绝对值。
   • 如果这个差值大于 max_diff，则更新 max_diff。
5. 返回 max_diff。

参考代码

• Python

def max_difference(nums):
    # 计算数组的总和
    total_sum = sum(nums)
    
    # 初始化左边和为0，右边和为总和
    left_sum = 0
    right_sum = total_sum
    
    # 初始化最大差值为负无穷大
    max_diff = float('-inf')
    
    # 遍历数组，除了最后一个元素
    for num in nums[:-1]:
        # 更新左右两边的和
        left_sum += num
        right_sum -= num
        
        # 计算当前差值并更新最大差值
        current_diff = abs(left_sum - right_sum)
        max_diff = max(max_diff, current_diff)
    
    return max_diff

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

# 计算并输出结果
result = max_difference(nums)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

long long max_difference(int* nums, int n) {
    // 计算数组的总和
    long long total_sum = 0;
    for (int i = 0; i < n; i++) {
        total_sum += nums[i];
    }
    
    // 初始化左边和为0，右边和为总和
    long long left_sum = 0;
    long long right_sum = total_sum;
    
    // 初始化最大差值为0
    long long max_diff = 0;
    
    // 遍历数组，除了最后一个元素
    for (int i = 0; i < n - 1; i++) {
        // 更新左右两边的和
        left_sum += nums[i];
        right_sum -= nums[i];
        
        // 计算当前差值并更新最大差值
        long long current_diff = llabs(left_sum - right_sum);
        if (current_diff > max_diff) {
            max_diff = current_diff;
        }
    }