Tsao chien
BAN USER#include <algorithm>
using namespace std;
int computMaxDiff(int *array,int len)
{
int *maxarray=new int[len];
int *minarray=new int[len];
maxarray[0]=array[0];
minarray[0]=-array[0];
int currentmax=maxarray[0]>0?array[0]:0;
int currentmin=minarray[0]>0?minarray[0]:0;
for(int i=1;i<len;i++)
{
currentmax+=array[i]; //max
maxarray[i]=max(currentmax,maxarray[i-1]);
if(currentmax<0) currentmax=0;
currentmin+=-array[i]; // max of -array
minarray[i]=max(currentmin,minarray[i-1]);
if(currentmin<0) currentmin=0;
}
for (int i=0;i<len;i++) //min of array
minarray[i]=-minarray[i];
int *revmaxarray=new int[len];
int *revminarray=new int[len];
revmaxarray[len-1]=array[len-1];
revminarray[len-1]=-array[len-1];
int revcurrentmax=revmaxarray[len-1]>0?revmaxarray[len-1]:0;
int revcurrentmin=revminarray[len-1]>0?revminarray[len-1]:0;
for(int i=len-2;i>=0;i--)
{
revcurrentmax+=array[i];
revmaxarray[i]=max(revcurrentmax,revmaxarray[i+1]);
if(revcurrentmax<0) revcurrentmax=0;
revcurrentmin+=-array[i];
revminarray[i]=max(revcurrentmin,revminarray[i+1]);
if(revcurrentmin<0) revcurrentmin=0;
}
for (int i=0;i<len;i++)
revminarray[i]=-revminarray[i];
int maxdiff=0;
for (int i=0;i<len;i++)
{
int currMax=max(abs(maxarray[i]-revminarray[i]),abs(minarray[i]-revmaxarray[i]));
if(currMax>maxdiff)
maxdiff=currMax;
}
return maxdiff;
}
int _tmain(int argc, _TCHAR* argv[])
{
int array[5]={-3,4,-1,4,5};
int maxdiff=computMaxDiff(array,5);
return 0;
}
how about "abc","abc"
- Tsao chien January 11, 2013
how about the buckets is not normative ?
- Tsao chien June 14, 2013