1847049_tle.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

int main()
{
 __int64  sum[100002], SUM, max;
 long i, j, p, n, a[100002], x, y, left[100002], right[100002];

 scanf("%ld",&n);
 sum[0] = 0;
 
 for(i = 1; i <= n; i++)
 {
	 scanf("%ld",&a[i]);
	 sum[i] = sum[i-1] + (__int64)a[i];
	 
 }
  for(i = 1; i <= n; i++)
  {
   j = i + 1;p = i - 1;
   while(a[i] <= a[j]&&j<=n)
	   j++;
   while(a[i] <= a[p]&&p)
		 p--;
   right[i] = j - 1;
   left[i] = p + 1;
  }
  max = -1;
 for(i = 1; i <= n; i++)
 {
    SUM = (sum[right[i]] - sum[left[i]] + a[left[i]])*a[i];
	if(SUM > max)
	{max = SUM;x = left[i];y = right[i];}
 }
 printf("%I64d\n%ld %ld\n",max,x,y);
 return 0;
}