分割数组的最大差值 - 华为OD机试题

小土豆Yuki

发布于 2024-07-15 09:25:13

500

发布于 2024-07-15 09:25:13

文章被收录于专栏：洁癖是一只狗

题目描述

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

输入描述

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

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

输出描述

输出差值的最大取值

示例一

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

输出：
10

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);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-07-14，如有侵权请联系 cloudcommunity@tencent.com 删除

数据