※ 引述《FRAXIS (喔喔)》之铭言：
: 这算是经典的最大连续子阵列和的变形吧。
: 给定一个长度为 n 的整数阵列，和一个正整数 k 。
: 找出一个在所有 C(n, 2) 个连续子阵列中，总和第 k 大的连续子阵列。
: 理论上是可以做到 O(n)，但是这方法应该不实用。
: 虽然也有其他的O(n lg n)，O(n lg^2 n)和O(n lg^3 n)的方法，
: 但是好像都不太实际 （O(n lg^3 n)的方法或许比较可行..）
: 我的问题是： 有没有实际上比较有效率（o(n^2)）且好实作的方法呢？
: 这问题是在 careercup 上看到的面试问题
: http://www.careercup.com/question?id=12804676
最近刚好有遇到类似的问题
我想你问的应该是静态问题而不是动态问题吧？
令 sum[i][j] = a[i] + ... + a[j] 是连续和
把 sum 画成一个矩阵
只有上三角，对角线是 a[0] 到 a[n-1]
整个结构类似 pascal 三角形，
不过这里是越右上越大，右上角是总和 a[0] + ... + a[n-1]
目标是从上三角当中找到第k大
之前在这个板有讨论过一个类似的问题：已排序阵列找第k大、row已排序阵列找第k大
┌─────────────────────────────────────┐
│ 文章代码(AID): #1KF5PfAs (Prob_Solve) [ptt.cc] [问题] 给定n个排好序的整? │
│ 文章网址: https://www.ptt.cc/bbs/Prob_Solve/M.1413240425.A.2B6.html │
│ 这一篇文章值 107 Ptt币 │
└─────────────────────────────────────┘
应该就是这样解吧？
只不过这个问题的阵列元素不是已知
所以要先算个前缀和，就能以O(1)时间求得阵列元素