分割数组的最大差值 - 华为OD统一考试

OD统一考试

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

输入描述

第一行输入数组Q中元素个数n，1< n < 100000

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

输出描述

输出差值的最大取值

示例1

输入：
6
1 -2 3 4 -9 7

输出：
10

题解

简单模拟题，需要小心的是数据范围。

Java

java">import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] nums = new int[n];
        long sum = 0;

        for (int i = 0; i < n; i++) {
            int num = scanner.nextInt();
            sum += num;
            nums[i] = num;
        }

        long maxAbs = 0, leftSum = 0;
        for (int i = 0; i < n - 1; i++) {
            leftSum += nums[i];

            // rightSum = sum - leftSum, 差值 = rightSum - leftSum = Math.abs(sum - leftSum)
            maxAbs = Math.max(maxAbs, Math.abs(sum - 2 * leftSum));
        }

        System.out.println(maxAbs);
    }
}

Python

python">n = int(input())
nums = list(map(int, input().split()))

sum_val,max_abs,left_sum = sum(nums),0,0

for i in range(n - 1):
    left_sum += nums[i]
    # right_sum = sum - left_sum, 差值 = right_sum - left_sum = abs(sum - left_sum)
    max_abs = max(max_abs, abs(sum_val - 2 * left_sum))

print(max_abs)

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    long long sum = 0;
    int n, num;
    cin >> n;
    vector<int> nums(n);
    for(int i=0; i<n; i++) {
        cin >> num;
        sum += num;
        nums[i] = num;
    }

    long long max_abs = 0, left_sum = 0;
    for(int i=0; i<n-1; i++) {
        left_sum += nums[i];

        // right_sum = sum - left_sum,  差值 = right_sum - left_sum = abs(sum - left_sum)
        max_abs = max(max_abs, abs(sum - 2 * left_sum));
    }

    cout << max_abs << endl;
}