When you have a nice algorithm from Googmeister in O(n log n).... why try something else...?
On 7/5/06, mg <[EMAIL PROTECTED]> wrote:
#include<stdio.h>
struct key {
int min;
double sum;
};
int main(int argc,char **argv)
{
int n,i,j,k;
int start=0,end=0;
double currentValue=0,eValue=0;
struct key opt[100000];
int a[100000];
while ( scanf("%d",&n) != EOF )
{
start = 0;
end = 0;
eValue = 0;
for ( i =0;i<n;i++)
{
scanf("%d",&a[i]);
opt[i].min = a[i];
opt[i].sum = a[i];
currentValue = opt[i].sum * opt[i].min;
if ( currentValue > eValue )
{
eValue = currentValue;
start = i;
end = i;
}
}
for( i = 0; i <= n -1; i++ )
{
for (j=i+1;j<=n-1;j++)
{
if(opt[i].min > a[j])
opt[i].min = a[j];
opt[i].sum += a[j];
currentValue = opt[i].sum * opt[i].min;
if ( currentValue > eValue )
{
eValue = currentValue;
start = i;
end = j;
}
}
}
printf("%.0f\n%d %d\n",eValue,start+1,end+1);
}
}
I am trying to get a better soln.
This one is n^2.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
