数组最大子数组和

  1 // maxofArray.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <iostream>
  6 using namespace std;
  7 #define N 11 
  8 int max_sub_array(int &s,int &e,int * a);
  9 int max_sub_array1(int &s,int &e,int * a);
 10 int max_sub_array2(int &s,int &e,int * a);
 11 int main()
 12 {
 13     int a[N]={31,-41,59,26,0,-53,58,97,-93,-23,84};
 14     int start,end;
 15     int sum = max_sub_array1(start,end,a);
 16     cout << sum << "  "<<start<< " "<<end<< endl;
 17     return 0;
 18 }
 19 int max_sub_array(int &s,int &e,int * a)
 20 {
 21     int i=0;
 22     int j,k =0;
 23     int b,start,end;
 24     int sum = 0;
 25     int max = a[0];
 26     s = e = start = end = 0;//sºÍeÊÇÕû¸öÊý×éa[0~n]µÄ×î´ó×Ó¶ÎµÄÆðÄ©Î»ÖÃ¡£startºÍendÊÇÊý×éa[0~i]µÄÆðÄ©Î»ÖÃ
 27     for(i = 0;i < N; i++)
 28     {
 29         
 30         for (j=i;j<N;j++){        
 31             for(k=i;k<=j;k++){
 32                 sum += a[k];
 33             }
 34             if(sum > max){
 35                 max = sum;
 36                 start = i;
 37                 end =j;
 38             }
 39             sum=0;
 40         }
 41     }
 42     s = start;
 43     e= end;
 44     return max;
 45 }
 46 //½â·¨Ò»¸Ä½ø°æ£º
 47 //×ÐÏ¸×ÁÄ¥¾Í»á·¢ÏÖ£¬ÆäÊµ²»ÐèÒªÔÙÊ¹ÓÃkÈ¥±éÀú×ÓÊý×é£¬ÒòÎªÃ¿´ÎjÒÆ¶¯¶¼»á²úÉúÐÂµÄ×ÓÊý×é£¬ËùÒÔÖ»ÒªÔÚÃ¿´ÎjÒÆ¶¯Ê±½øÐÐÒ»ÏÂ±È½Ï£¬¾Í²»»á°Ñ×î´óÖµÂ©µô¡£ËùÒÔÖ»ÓÐiºÍjÒÆ¶¯£¬¸´ÔÓ¶È½µµÍµ½O£¨n^2£©¡£
 48 //´úÂëÈçÏÂ£º
 49 int max_sub_array1(int &s,int &e,int * a)
 50 {
 51     int i=0;
 52     int j,k =0;
 53     int start,end;
 54     int sum = 0;
 55     int max = a[0];
 56     s = e = start = end = 0;//sºÍeÊÇÕû¸öÊý×éa[0~n]µÄ×î´ó×Ó¶ÎµÄÆðÄ©Î»ÖÃ¡£startºÍendÊÇÊý×éa[0~i]µÄÆðÄ©Î»ÖÃ
 57     for(i = 0;i < N; i++)
 58     {
 59         sum=0;
 60         for (j=i;j<N;j++){        
 61             sum+=a[j];
 62             if(sum > max){
 63                 max = sum;
 64                 start = i;
 65                 end =j;
 66             }
 67         }
 68     }
 69     s = start;
 70     e= end;
 71     return max;
 72 }
 73 int max_sub_array2(int &s,int &e,int * a)
 74 {
 75     int i=0;
 76     int j =0;
 77     int b,start,end;
 78     int sum = 0;
 79     sum = b = a[0];
 80     s = e = start = end = 0;//sºÍeÊÇÕû¸öÊý×éa[0~n]µÄ×î´ó×Ó¶ÎµÄÆðÄ©Î»ÖÃ¡£startºÍendÊÇÊý×éa[0~i]µÄÆðÄ©Î»ÖÃ¡£
 81     for(i = 1;i<N;i++)
 82     {
 83         if(b>0)
 84         {
 85             b = b + a[i];
 86             end = i;
 87         }
 88         else
 89         {
 90             b = a[i];
 91             start = end = i;
 92         }
 93         if(sum<b)
 94         {
 95             sum = b;
 96             s = start;
 97             e = end;
 98         }
 99     }
100     return sum;
101 }