题目描述
给定一个由若干整数组成的数组nums ，可以在数组内的任意位置进行分割，将该数组分割成两个非空子数组（即左数组和右数组），分别对子数组求和得到两个值，计算这两个值的差值，请输出所有分割方案中，差值最大的值。
输入描述
第一行输入数组中元素个数n，1 < n <= 100000
第二行输入数字序列，以空格进行分隔，数字取值为4字节整数
输出描述
输出差值的最大取值
示例
输入
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,1]` 且 `右数组 =[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
题解
暴力求解时间复杂度为O(n^2)，容易超时。
还可以使用前缀和方式求解，时间复杂度O(n)。
/*
* @hw id=2023B lang=cpp
*
* 分割数组的最大差值
*/
// @hw code=start
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int nums[n];
int lsum = 0, rsum = 0, ans = 0;
for(int i=0;i<n;i++) {
cin >> nums[i];
rsum += nums[i];
}
for(int i=0;i<n;i++) {
lsum += nums[i];
rsum -= nums[i];
ans = max(ans, abs(lsum - rsum));
}
cout << ans << endl;
return 0;
}
// @hw code=end
/*
* @hw id=2023B lang=java
*
* 分割数组的最大差值
*/
// @hw code=start
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
int rsum = 0, lsum = 0, ans = 0;
for(int i=0;i<n;i++) {
nums[i] = in.nextInt();
rsum += nums[i];
}
for(int i=0;i<n;i++) {
lsum += nums[i];
rsum -= nums[i];
ans = Math.max(ans, Math.abs(lsum - rsum));
}
System.out.println(ans);
}
}
// @hw code=end
#
# @hw id=2023B lang=python3
#
# 分割数组的最大差值
#
# @hw code=start
n = int(input())
nums = list(map(int, input().split()))
lsum = 0
rsum = sum(nums)
ans = 0
for i, num in enumerate(nums):
lsum += num
rsum -= num
ans = max(ans, abs(lsum - rsum))
print(ans)
# @hw code=end