c**********e
发帖数: 2007 | 1 Suppose you have an array of integers a[0],...,a[n]. Design an algorithm
to find the maximum sum of any contiguous subarray. Optimize speed. | l*******r
发帖数: 511 | 2 for i=1 to n
maxendinghere=max(maxendinghere+x_i,0)
maxsofar=max(maxsofar,maxendinghere)
【在 c**********e 的大作中提到】
: Suppose you have an array of integers a[0],...,a[n]. Design an algorithm
: to find the maximum sum of any contiguous subarray. Optimize speed.
| c**********e
发帖数: 2007 | 3 The following code is from a book. But it does not work.
I have not been able to make it work. Anybody look at it?
________________________________
#include
#include
using namespace std;
int maxSub(int a[], int n, int& i, int& j) {
int t=a[0], vmax = a[0];
int tmin = min(0, t);
for(int k=1; k
{
t+=a[k];
if(t-tmin > vmax) { vmax = t-tmin; j=k; }
if(t < tmin) { tmin =t; i=(k+1
}
return vmax;
}
int main() { |
|
