链接:https://ac.nowcoder.com/acm/contest/67743/E
来源:牛客网
智乃最近学习了冒泡排序和最长子段和,所以她现在想把它们合并成一个新的算法。
众所周知,冒泡排序是一种通过交换相邻元素实现排序的算法,最长子段和是指从一个数组aaa中取出一段连续的非空数组区间[l,r][l,r][l,r],最大化数组区间的和∑i=lrai\sum_{i=l}^{r}a_{i}∑i=lrai。
现在智乃有一个长度大小为NNN的数组,数组中元素的值有正有负。她想要先进行恰好KKK次相邻元素的交换操作,再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大,请你帮助智乃算出她最终可能的最大子段和有多大。
输入描述:
第一行输入两个正整数N,K(2≤N≤103,0≤K≤100)N,K(2\leq N \leq 10^3,0 \leq K \leq 100)N,K(2≤N≤103,0≤K≤100)表示数组的长度,交换的次数。
接下来一行NNN个整数,输入数组元素ai(−109≤ai≤109)a_i(-10^{9} \leq a_{i} \leq 10^{9})ai(−109≤ai≤109)表示数组元素的值。
输出描述:
仅一行一个整数,表示交换后能取到的非空最大子段和是多少。
示例1
输入
[复制](javascript:void(0)
标签:比赛,leq,1000000000,子段,交换,牛客,数组,100,2.7 From: https://www.cnblogs.com/HLZZPawa/p/18013738