1847576_ac_367ms_1984k.c

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

# include <stdio.h>


int main()
{
 __int64  sum[100002], SUM, max;
 long i, j, 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] + a[i];
     j = i - 1;
     while(j&&a[i] <= a[j])
		 j = left[j] - 1;
     left[i] = j + 1;
 }
  for(i = n; i >= 0; i--)
  {
   j = i + 1;
   while(j<=n&&a[i] <= a[j])
       j = right[j] + 1;
   right[i] = j - 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;
}