#include <stdio.h>
/*
 *@function:找出数组中连续子数组最大和
 *@param     arr: 数组指针
 *@param    size: 数组长度
 *@param    left: 返回连续子数组的左下标
 *@param   right: 返回连续子数组的右下标
 *@retval:整数串中连续子数组最大和
 */
int seek_max_string(int arr[], int size, int *left, int *right)
{     int a,b,max = -0x7fffffff,ans=0;     for(int i=0; i<size; i++)     {         for(int j=i; j<size; j++)         {             ans += arr[j];             if(ans > max)                 max=ans,*left=i,*right=j;         }         ans=0;     }     return max;
}

/*
 *@function:找出数组下标从left->right中最小值
 *@param     arr: 数组指针
 *@param    left: 左下标
 *@param   right: 右下标
 *@retval:数组中最小值
 */
int seek_min_number(int arr[], int left, int right)
{     int min=0x7fffffff;     for(int i=left; i<=right; i++)     {             if(min > arr[i])                 min=arr[i];     }     return min;
}


int main()
{     int N;     while(scanf("%d",&N) != EOF){         int arr[N];         for(int i=0; i<N; i++)             scanf("%d",&arr[i]);         int left,right,max,min;         int a,b,c,d,second_max=0,third_max=0,sub_max=0;//sub_max:第二个子串和最大值                  max = seek_max_string(arr, N, &left, &right);         min = seek_min_number(arr, left, right);                  /*          *找到的子数组分四种情况（1）子数组在数组中间（2）子数组就是数组（3）子数组在数组最左（4）子数组在数组最右          *四种情况分别找寻第二子数组          */         if(left != 0 && right != N-1)         {             second_max = seek_max_string(arr,         left-1,    &a, &b);             third_max  = seek_max_string(arr+right+1, N-right-1, &c, &d);             sub_max = second_max>third_max? second_max:third_max;         }         else if(left == 0 && right == N-1){             sub_max = 0;         }         else if(left != 0 && right == N-1){             second_max = seek_max_string(arr,     left,   &a, &b);             sub_max = second_max;         }         else if(left == 0 && right != N-1){             int *left_arr = arr;             third_max  = seek_max_string(left_arr+right+1, N-right-1, &c, &d);             sub_max = third_max;         }                                       if(min+sub_max >= 0 || (max < 0 && sub_max<0)) //  需要找两个子数组              printf("%d\n", max+sub_max);         else                               //  找到的第一个数组包含两个最大子数组             printf("%d\n", max-min);     }     return 0;
}