煜最近学习了冒泡排序和最长子段和，所以她现在想把它们合并成一个新的算法。
众所周知，冒泡排序是一种通过交换相邻元素实现排序的算法，最长子段和是指从一个数组a中取出一段连续的非空数组区间[l,r]，最大化数组区间的和(al+al+1+a...+ar-1+ar)。
现在煜有一个长度大小为N的数组，数组中元素的值有正有负。她想要先进行恰好K次相邻元素的交换操作，再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大，请你帮助煜算出她最终可能的最大子段和有多大。
3120: 最大子段和
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 3
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行输入两个正整数N,K(2≤N≤103,0≤K≤1)表示数组的长度，交换的次数。
接下来一行N个整数，输入数组元素ai(−109≤ai≤109)表示数组元素的值。
接下来一行N个整数，输入数组元素ai(−109≤ai≤109)表示数组元素的值。
输出描述
仅一行一个整数，表示交换后能取到的非空最大子段和是多少。
样例输入
5 0
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000样例输出
-1000000000提示
输入:
5 1
5 4 -100 2 3
输出:
11
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版