※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413240425.A.2B6.html │ │ 这一篇文章值 107 Ptt币 │ └─────────────────────────────────────┘ 应该就是这样解吧？ 只不过这个问题的阵列元素不是已知 所以要先算个前缀和，就能以O(1)时间求得阵列元素 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.79.38 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1425079575.A.53B.html ※ 编辑: DJWS (111.250.79.38), 02/28/2015 07:34:55 ※ 编辑: DJWS (111.250.79.38), 02/28/2015 07:46:31