【华为OD-E卷 - 120 分割数组的最大差值 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 分割数组的最大差值 100分（python、java、c++、js、c）】

题目

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

输入描述

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

输出描述

  • 输出差值的最大取值

用例

用例一：
输入：
6
1 -2 3 4 -9 7
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
输出：
10
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1

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)  # 输出最大差值

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

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);  // 输出最大差值
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

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;  // 返回最大差值
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145143181"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！