会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要求「所有连续子数组和」中第 K 大的值，数组长度 n≤1000，K 不超过子数组总数 n(n+1)/2≤500500。
第一步：把「子数组和」变成「两个前缀和之差」。记 pref[0]=0、pref[i]=a[0]+a[1]+⋯+a[i−1]，则区间 [i,j]（0≤i≤j≤n−1）的和为
S(i,j)=pref[j+1]−pref[i].
第二步：枚举全部 n(n+1)/2 个区间。 用两重循环枚举左端点 i 与右端点对应的前缀下标 j+1，把 S(i,j) 全部收集起来。n=1000 时共 1000×1001/2=500500 个数，完全存得下。
题目内容
小张是一名金融交易员，现在记录了某只股票连续 n 个交易日每天的“涨跌金额”（上涨为正、下跌为负、横盘为 0）；如果某次交易是“在某个交易日买入、之后某个交易日卖出”，那么这笔交易的利润就等于这两个交易日之间（含买入日与卖出日）所有日子的涨跌金额之和。
小张正在设计一个交易策略，想找出所有可行交易时段里，利润排名第 K 大的那个利润值，以此观察收益分布。
请你设计一个程序，帮小张求出这个第 K 大的交易利润值。
注意：
- 一次交易为「买入日 i → 卖出日 j（0≤i≤j≤n−1）」，利润 =a[i]+a[i+1]+⋯+a[j]；
- 只要买入日 / 卖出日不同就视为不同交易时段；利润相同的不同时段也分别计入排名（并列依次占用排名）；
- 数组可包含负数，因此利润可正、可负、可为 0，均按排名取第 K 大的值。
输入描述
输入包含一行，格式为 [a0, a1, ..., a(n-1)],K：先给出一个用方括号包裹、以逗号分隔的整数数组 a，方括号之后紧跟一个半角逗号，再给出整数 K。逗号之后可能带有空格（样例1 即为这种写法），你的读入代码需要容忍任意空白。
例如样例1 的输入为 [3, -2, 5],3，表示 a=[3,−2,5]、K=3。
取值范围：
- 1≤n≤1000（n 为数组长度）
- −109≤a[i]≤109
- 1≤K≤n(n+1)/2，即 K 不超过全部连续子数组的个数
输出描述
输出一行一个整数，表示所有连续子数组和按从大到小排序后第 K 大的那个值；相同的值并列，各占一个名次。
64 位说明：子数组和的绝对值最大可达 1000×109=1012，已超出 32 位有符号整数范围，答案在 64 位整数范围内。请按 64 位整数返回与运算：C++ 用 long long、Java 用 long、Python 用 int、JavaScript 用 number、C 用 long long；中间的「前缀和 / 区间和 / 累加」也必须用 64 位，用 int 会溢出。
样例1
输入
[3, -2, 5],3
输出
3
说明
所有可行交易利润为 [3]=3、[-2]=-2、[5]=5、[3,-2]=1、[-2,5]=3、[3,-2,5]=6，按从大到小为 6, 5, 3, 3, 1, -2；重复的 3 各占一位，从大到小第 3 大为 3。
样例2
输入
[1, 2, 3],1
输出
6
说明
利润最大的一段就是整个记录 1+2+3=6，即第 1 大为 6。
样例3
输入
[-5, -2, -1, -3],2
输出
-2
说明
全部交易利润从大到小为 -1, -2, -3, -3, -4, -5, -6, -7, -8, -11，第 2 大为 -2（即便全是亏损，也照样按排名取值）。
