c*****z
发帖数: 182 | 1 假设一个数组a[N],有N个实数存在里面，有正有负
想找到两个index，i和j，使得a[i]+a[i+1]+...+a[j]
的和是所有可能的i，j中最大的，请问这个有什么比
O(N^2)快的方法吗，谢谢了 |
i******r
发帖数: 323 | 2 动态规划
假设N > 0
double max, curr=-1;
int maxI = -1, maxJ; //use maxI == -1 to denote that max = -infinity
int currI;
for (int i = 0; i < N; ++i) {
if (curr < 0) {
curr = 0;
currI = i;
}
curr = curr + a[i];
if (maxI < 0 || curr > max) {
maxI = currI;
maxJ = i;
max = curr;
}
}
//now maxI and maxJ is what you want
//complexity O(N)
【在 c*****z 的大作中提到】
: 假设一个数组a[N],有N个实数存在里面，有正有负
: 想找到两个index，i和j，使得a[i]+a[i+1]+...+a[j]
: 的和是所有可能的i，j中最大的，请问这个有什么比
: O(N^2)快的方法吗，谢谢了
|
b***y
发帖数: 2799 | 3 Programming Pearls, Column 8, Scanning Algorithm.
O(n).
【在 c*****z 的大作中提到】
: 假设一个数组a[N],有N个实数存在里面，有正有负
: 想找到两个index，i和j，使得a[i]+a[i+1]+...+a[j]
: 的和是所有可能的i，j中最大的，请问这个有什么比
: O(N^2)快的方法吗，谢谢了
|
c*****z
发帖数: 182 | 4 多谢多谢，我觉得好像在那儿看过的，呵呵
【在 b***y 的大作中提到】
: Programming Pearls, Column 8, Scanning Algorithm.
: O(n).
|
n****g
发帖数: 150 | 5 这个不挺好的吗？
【在 i******r 的大作中提到】
: 动态规划
: 假设N > 0
: double max, curr=-1;
: int maxI = -1, maxJ; //use maxI == -1 to denote that max = -infinity
: int currI;
: for (int i = 0; i < N; ++i) {
: if (curr < 0) {
: curr = 0;
: currI = i;
: }
|
i******r
发帖数: 323 | 6 握手～
【在 n****g 的大作中提到】
: 这个不挺好的吗？
|
