You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int INF = 0x3f3f3f3f ;
const int N = 200010 ;
int n ;
int a [ N ] ;
//分治函数
int rec ( int l , int r ) {
//递归的出口
if ( l = = r ) return a [ l ] ; // l=r时，
int mid = ( l + r ) > > 1 ; //中间点
// [l..mid]区间内包含mid的最大后缀和
int sum = 0 , lmax = - INF , rmax = - INF ;
for ( int i = mid ; i > = l ; i - - ) sum + = a [ i ] , lmax = max ( lmax , sum ) ;
// [mid+1..r]区间内包含(mid+1)的最大前缀和
sum = 0 ;
for ( int i = mid + 1 ; i < = r ; i + + ) sum + = a [ i ] , rmax = max ( rmax , sum ) ;
//三种可能取最大值
return max ( max ( rec ( l , mid ) , rec ( mid + 1 , r ) ) , lmax + rmax ) ;
}
int main ( ) {
cin > > n ;
for ( int i = 1 ; i < = n ; i + + ) cin > > a [ i ] ;
printf ( " %d " , rec ( 1 , n ) ) ; //在范围1~n之间求最大子段和
return 0 ;
}
