C++:最大子数组差
2024-09-01 19:16:06
最大子数组差
内存限制:128 MiB 时间限制:1000 ms
题目描述:
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B) |最大。
输出这个最大的差值。
输入:
共两行。
第一行:一个整数n,表示整数数组的长度。
第二行:n个整数。(每个数的绝对值不大于1e4)
输出:
最大的差值。
样例输入:
样例1输入:
4
1 2 -3 1
样例1输出:
6
样例2输入:
7
2
-1 -2 1 -4 2 8
样例2输出:
16
数据范围与提示:
n <= 1e5
在领扣(Lintcode)海题时候海到的,有点动态规划的意思。
人话点说,就是找到一串最大的连续子数组与另一串不重叠的最小子数组,然后把它们相减,取绝对值。感觉我在废话
什么是子数组呢?
比如:数组a为 2, 3,13, 5,235, 3251, 33, 25;
3, 13, 5, 235就是数组a的子数组;
拿出你的小脑袋瓜思考一下,最大子数组与最小子数组的分布会不会有以下情况:
想好了吗?
答案是:不会
如果中间那段是正数的话,应该和最大子数组一起,对吧
如果是负数的话,就应该放到最小子数组:
如果是零,放哪边都无所谓
综上,我们可以得出:最大子数组和最小子数组是相邻的
如何使|SUM(A)-SUM(B)|尽可能大,我们要做讨论
当A是大数时,如①
当B是大数时,如②
A从终点往左找最大值/最小值,B从起点往右找最小值/最大值
我好像什么都没说,又好像什么都说了,终于分析完了,要码到头晕了
完整代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n, a[100010], amax[MAXN], amin[MAXN], bmax[MAXN], bmin[MAXN], intmin=-214748367;
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
amax[i]=max(a[i], amax[i-1]+a[i]);//求SUM(A)最大值
amin[i]=min(a[i], amin[i-1]+a[i]);//求SUM(A)最小值
}
for(int i=n;i>=1;i--){
bmax[i]=max(a[i], bmax[i+1]+a[i]);//求SUM(B)最大值
bmin[i]=min(a[i], bmin[i+1]+a[i]);//求SUM(B)最大值
}
for(int i=1;i<=n-1;i++){
if(abs(amax[i]-bmin[i+1])>maxn)maxn=amax[i]-bmin[i+1];//当SUM(A)是大数时
}
for(int i=n;i>=2;i--){
if(abs(bmax[i]-amin[i-1])>maxn)maxn=bmax[i]-amin[i-1];//当SUM(B)是大数时
}
printf("%d", maxn);
return 0;
}
老规矩,抵制学术不端行为,拒绝Ctrl+c
呵,又是苟延残喘的一天~
最新文章
- C#基础篇 - 正则表达式入门
- JSON与String 格式的转换
- VS大视野
- ZooKeeper配置管理文件
- 实战微信JS SDK开发:贺卡制作与播放(1)
- 你应该了解的jquery 验证框架
- vs转eclipse之工具快速上手篇
- CAF(C++ actor framework)使用随笔(使用类去构建actor和使用的一些思路)
- 关于position和float的用法!
- HUST 1605 Gene recombination
- 2016 ICPC总结
- SuperSocket入门(四)-命令行协议
- selenium之 webdriver与三大浏览器版本映射表(更新至v2.29)
- Jquery常用的方法总结
- mmap映射区和shm共享内存的区别总结
- 【洛谷P3792】由乃与大母神原型和偶像崇拜
- PAT-GPLT训练集 L2-001 紧急救援(最短路)
- vux在ISO中异常 this.$vux.confirm.show
- 使用Android Studio自带的NDK编译JNI
- file_put_contents(): supplied resource is not a valid stream resource