0001 #include "sum/sum.h"
0002 extern int s_lo, s_hi;
0003 
0004 int gs_BF( int A[], int n ) { //蛮力策略：O(n^3)
0005    int gs = A[0]; s_lo = 0; s_hi = 1;
0006    for ( int lo = 0; lo < n; lo++ ) //枚举所有的
0007       for ( int hi = lo; hi < n; ) { //O(n^2)个区段
0008          int s = sum(A, lo, ++hi); //用O(n)时间求和（改用sum(A+lo,++hi-lo)空间效率更高）
0009          if ( gs < s )
0010             { gs = s; s_lo = lo; s_hi = hi; } //择优、更新
0011       }
0012    return gs;
0013 }