- #include <stdio.h>
- /* O(N^2) */
- void naive_max_sum(int a[], int alen, int& best, int& besti, int& bestj){
- int i=0, j=0, s=0;
- best = 0;
- for(i=0;i<alen;i++){
- s=0;
- for(j=i;j<alen;j++){
- s += a[j];
- if(s>=best){
- best = s;
- besti = i;
- bestj = j;
- }
- }
- }
- }
- int dc_maxsum_r(int a[], int left, int right, int& besti, int& bestj){
- int center = (left+right)/2;
- if(left == right)
- return a[left]<0?0:a[left];
- int lbesti, lbestj, rbesti, rbestj, best;
- int sleft = dc_maxsum_r(a, left, center, lbesti, lbestj);
- int sright = dc_maxsum_r(a, center+1, right, rbesti, rbestj);
- int sl = 0, sr = 0, slmax = 0, srmax = 0, i=0, j=0;
- int slmax_i, srmax_j;
- for(i=center;i>=left;i--){
- sl += a[i];
- if(sl>slmax){
- slmax = sl;
- slmax_i = i;
- }
- }
- for(j=center+1;j<=right;j++){
- sr += a[j];
- if(sr > srmax){
- srmax = sr;
- srmax_j = j;
- }
- }
- if(sleft >= sright){
- besti = lbesti;
- bestj = lbestj;
- best = sleft;
- }else{
- besti = rbesti;
- bestj = rbestj;
- best = sright;
- }
- if( slmax+srmax > best){
- best = slmax+srmax;
- besti = slmax_i;
- bestj = srmax_j;
- }
- return best;
- }
- /* divide and conquer. O(NlogN) */
- int divide_conqer_maxsum(int a[], int alen, int& best, int& besti, int& bestj){
- best = dc_maxsum_r(a, 0, alen-1, besti, bestj);
- }
- /* Dynamic Program. O(N) */
- void dp_maxsum(int a[], int alen, int& best, int& besti, int&bestj){
- int s=0, b=0, i=0;
- for(i=0; i < alen; i++){
- if(b<0){
- b = a[i];
- besti = i;
- }else{
- b += a[i];
- }
- if(b>s){
- s = b;
- bestj = i;
- }
- }
- best=s;
- }
- void max_sum(int a[], int alen, int& best, int& besti, int& bestj){
- naive_max_sum(a, alen, best, besti, bestj);
- printf("best=%d, besti=%d, bestj=%d\\n", best, besti, bestj);
- divide_conqer_maxsum(a, alen, best, besti, bestj);
- printf("best=%d, besti=%d, bestj=%d\\n", best, besti, bestj);
- dp_maxsum(a, alen, best, besti, bestj);
- printf("best=%d, besti=%d, bestj=%d\\n", best, besti, bestj);
- }
- int main(){
- int a[] = {1,4,9,-3,-10, 2, -5, 1, 7, 6, -5, -2, 13, -2};
- int alen = sizeof(a)/sizeof(int);
- int best, besti, bestj;
- max_sum(a, alen, best, besti, bestj);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/040520149466.html
来源: http://www.codesnippet.cn/detail/040520149466.html