【华为OD】D卷真题100分：分割数组的最大差值 Java代码实现[思路+代码]

【华为OD】2024年C、D卷真题集：最新的真题集题库 C/C++/Java/python/JavaScript

【华为OD】2024年C、D卷真题集：最新的真题集题库 C/C++/Java/python/JavaScript-CSDN博客

JS、Java、python、C、C++代码实现：

【华为OD】D卷真题100分：分割数组的最大差值 JavaScript代码实现[思路+代码]-CSDN博客

【华为OD】D卷真题100分：分割数组的最大差值 Java代码实现[思路+代码]-CSDN博客

【华为OD】D卷真题100分：分割数组的最大差值 python代码实现[思路+代码]-CSDN博客

【华为OD】D卷真题100分：分割数组的最大差值 C语言代码实现[思路+代码]-CSDN博客

【华为OD】D卷真题100分：分割数组的最大差值 C++代码实现[思路+代码]-CSDN博客

题目描述：

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

输入描述

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

输出描述

输出差值的最大取值

示例1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

6
1 -2 3 4 -9 7

输出

10

说明

将数组 nums 划分为两个非空数组的可行方案有：
左数组 = [1] 且 右数组 = [-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] 且 右数组 = [7]，和的差值 = |-3 - 7   | = 10 
最大的差值为10

     7878688                                                         
                                                            
              +---+                                                          
  3            |   |       ++                               +       +---|   
  |           |   | 3      +                6               +  |   +   |        +
  |      +     |   |       +         +                      +    |  +   |       +
  |      +    |   +---+    +        +        +++++          +   +  +   |        +
  |      +    | +      |   +   +----+        |   |          +   +  +   |        +
  |      +  3 | +      |   +   +    +      2 |   |     2    +   +  +   |        +
  |      +    | +      |   +   +    +        |   |          +   +  +   |        +
  |      +---+ +     |    |  |    +    ----+   |   +---+    |  |  +   |         +
  |      |     +     |    |  |    +    |       |   |   |    |  |  +   |         +
  |    1 |     +     | 8  |  |    +  1 |   |    | 1 |   | 1 |   |  +   |        +
  |      |     +     |    |  |    +    |   |    |   |   |   |   |  +   |        +
  |  +---+     +     +---+   |    ++---+    ++   +---+   +---+   |  +   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  |0 |         +         | 0 |  0 |         ++              | 0 |  |+   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  +---+         +          +-------+                       +---+| +|+   |        +
                +                                                    +   |        +
    0   1   2   3   4   5   6   7   8   9  10  11  12 + v:    w  u m    u 1 0 2 4
 

题目解析：

        按逻辑来求和之后，再去求差值，找到最大差值即可

代码实现：

import java.util.Scanner;
import java.util.ArrayList;

public class Main {

    public static long read(ArrayList<Integer> arr, long sum) {
        long res = 0;
        long total = 0;
        for (int i = 0; i < arr.size() - 1; i++) {
            total += arr.get(i);
            res = Math.max(Math.abs(sum - 2 * total), res);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        long total = 0;

        for (int i = 0; i < n; i++) {
            arr.add(scanner.nextInt());
            total += arr.get(i);
        }

        System.out.println(read(arr, total));

        scanner.close();
    }
}