我在 CS.SE 上问过这个问题，但没有得到回应。
我最近面临以下面试问题：
给定一个数组 A 和一个整数 k，找到一个具有最大和的连续子数组，加上约束，这个子数组的长度最多为 k。
所以，如果A=[8, -1, -1, 4, -2, -3, 5, 6, -3]我们得到以下不同值的答案k：
+---+------------------------------+
| k | subarray |
+---+------------------------------+
| 1 | [8] |
| 7 | [5,6] |
| 8 | [8, -1, -1, 4, -2, -3, 5, 6] |
+---+------------------------------+
如果n是数组的长度A，那么使用修改后的优先级队列，我能够及时回答这个问题O(n lgk)；有没有办法改善这一点O(n)？请注意，O(n)当 k=n 时，Kadane 算法会及时运行。