>>473
O(n)の例。rightに入る値が>>472より一つ大きいのに注意。
int candidate(int a[], int size, int *left, int *right)
{
  int sum = 0;
  for(*left = 0; *left < size && a[*left] < 0; (*left)++);
  if(*left == size)
    return 0;
  for(*right = *left; *right < size && a[*right] > 0; (*right)++)
    sum += a[*right];
  return sum;
}
void search(int a[], int *left, int *right)
{
  int cl, cr, csum, i, sum = INT_MIN;
  for(i = 0; csum = candidate(a + i, NUM - i, &cl, &cr); i += cr)
    if(csum > sum)
    {
      *left = cl + i;
      *right = cr + i;
      sum = csum;
    }
  if(sum < 0) /* 正の数が一つもなかった。*/
    for(i = 0; i < NUM; i++)
      if(a[i] >= sum)
      {
        *left = i;
        *right = i + 1;
        sum = a[i];
      }
}