【华为OD-E卷 - 120 分割数组的最大差值 100分（python、java、c++、js、c）】
【华为OD-E卷 - 分割数组的最大差值 100分（python、java、c++、js、c）】
题目
给定一个由若干整数组成的数组nums ，可以在数组内的任意位置进行分割，将该数组分割成两个非空子数组（即左数组和右数组），分别对子数组求和得到两个值，计算这两个值的差值，请输出所有分割方案中，差值最大的值
输入描述
- 第一行输入数组中元素个数n，1 < n ≤ 100000 第二行输入数字序列，以空格进行分隔，数字取值为4字节整数
输出描述
- 输出差值的最大取值
用例
用例一：
输入：
6
1 -2 3 4 -9 7
输出：
10
python解法
- 解题思路：
- 这段代码的目的是在一个整数数组中找到将数组分成两部分时，前半部分和后半部分的绝对和差的最大值。
步骤解析：
输入处理：
n 表示数组的长度。
nums 是输入的整数数组。
前缀和与后缀和计算：
前缀和（prefix_sum）：prefix_sum[i] 表示从数组开始到第 i 个元素的总和。
后缀和（suffix_sum）：suffix_sum[i] 表示从第 i 个元素到数组末尾的总和。
计算最大差值：
遍历每个可能的分割点 i，计算 prefix_sum[i] 和 suffix_sum[i+1] 的差值，取其绝对值。
找出所有可能差值中的最大值。
输出结果：
输出找到的最大差值
n = int(input()) # 输入数组长度
nums = list(map(int, input().split())) # 输入数组元素
# 初始化前缀和和后缀和数组
prefix_sum = [0] * n # 前缀和数组，prefix_sum[i]表示从0到i的元素和
suffix_sum = [0] * n # 后缀和数组，suffix_sum[i]表示从i到n-1的元素和
# 计算前缀和
prefix_sum[0] = nums[0] # 第一个元素的前缀和就是它本身
for i in range(1, n):
prefix_sum[i] = prefix_sum[i-1] + nums[i] # 当前前缀和 = 前一个前缀和 + 当前元素
# 计算后缀和
suffix_sum[n-1] = nums[n-1] # 最后一个元素的后缀和就是它本身
for i in range(n-2, -1, -1): # 从倒数第二个元素开始计算
suffix_sum[i] = suffix_sum[i+1] + nums[i] # 当前后缀和 = 后一个后缀和 + 当前元素
# 计算最大差值
max_diff = 0 # 初始化最大差值
for i in range(n-1): # 遍历每个可能的分割点
diff = abs(prefix_sum[i] - suffix_sum[i+1]) # 计算当前分割的前缀和和后缀和的差值
max_diff = max(max_diff, diff) # 更新最大差值
print(max_diff) # 输出最大差值
java解法
- 解题思路
- 该代码的目标是将一个长度为 n 的整数数组分成两部分，找出这两部分元素和的最大绝对差值。
步骤解析：
输入处理：
首先读取整数 n，表示数组的长度。
然后读取 n 个长整型数，存入数组 arr。
前缀和计算：
使用 prefixSum 数组来存储前缀和，prefixSum[i] 表示从数组开始到第 i 个元素的总和。
这样可以在 O(1) 时间内获取任意位置的前半部分和。
总和计算：
数组所有元素的总和为 totalSum，等于 prefixSum[n - 1]。
计算最大差值：
遍历所有可能的分割点（从索引 0 到 n - 2）。
对于每个分割点 i：
左部分的和：leftSum = prefixSum[i]。
右部分的和：rightSum = totalSum - leftSum。
计算两部分和的差值：diff = |leftSum - rightSum|。
更新最大差值 maxDiff。
输出结果：
输出计算得到的最大差值
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 输入数组长度
long[] arr = new long[n]; // 存储输入的数组
long[] prefixSum = new long[n]; // 存储前缀和
// 读取输入并计算前缀和
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong(); // 读取第 i 个元素
// 当前前缀和 = 当前元素 + 前一个前缀和（若 i == 0 则直接取当前元素）
prefixSum[i] = arr[i] + (i > 0 ? prefixSum[i - 1] : 0);
}
long totalSum = prefixSum[n - 1]; // 数组的总和，即最后一个前缀和
long maxDiff = 0; // 初始化最大差值
// 遍历所有分割点，计算最大差值
for (int i = 0; i < n - 1; i++) {
long leftSum = prefixSum[i]; // 左半部分的和
long rightSum = totalSum - leftSum; // 右半部分的和
long diff = Math.abs(leftSum - rightSum); // 计算两部分的绝对差值
if (diff > maxDiff) { // 更新最大差值
maxDiff = diff;
}
}
System.out.println(maxDiff); // 输出最大差值
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
具体步骤：
输入处理：
通过 readline 模块从标准输入读取一行数据。
将输入的字符串按空格分割成数字数组 nums。
前缀和与后缀和计算：
前缀和 (prefixSum)： prefixSum[i] 表示从数组开始到第 i 个元素的总和。
后缀和 (suffixSum)： suffixSum[i] 表示从第 i 个元素到数组末尾的总和。
计算最大差值：
遍历所有可能的分割点 i，计算 prefixSum[i] 和 suffixSum[i + 1] 的差值，取其绝对值。
找出所有差值中的最大值。
输出结果：
输出最大差值
const readline = require("readline");
// 创建 readline 接口，读取标准输入
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 监听输入事件，处理输入数据
rl.on("line", (line) => {
const nums = line.split(" ").map(Number); // 将输入按空格分割，并转换为数字数组
if (nums.length > 1) { // 当数组长度大于1时才进行处理
console.log(maxDifference(nums)); // 计算并输出最大差值
}
});
/**
* 计算数组分割后的最大绝对差值
*
* @param {number[]} arr - 输入的整数数组
* @returns {number} - 返回最大差值
*/
function maxDifference(arr) {
const n = arr.length;
const prefixSum = new Array(n).fill(0); // 初始化前缀和数组
const suffixSum = new Array(n).fill(0); // 初始化后缀和数组
// 计算前缀和
prefixSum[0] = arr[0];
for (let i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i]; // 当前前缀和 = 前一个前缀和 + 当前元素
}
// 计算后缀和
suffixSum[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--) {
suffixSum[i] = suffixSum[i + 1] + arr[i]; // 当前后缀和 = 后一个后缀和 + 当前元素
}
// 计算最大差值
let maxDiff = 0;
for (let i = 0; i < n - 1; i++) {
const diff = Math.abs(prefixSum[i] - suffixSum[i + 1]); // 计算当前分割的绝对差值
maxDiff = Math.max(maxDiff, diff); // 更新最大差值
}
return maxDiff; // 返回最大差值
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏