程序员的博客: 2_14

2011年6月21日星期二

   1:  // 2_14最大子段和.cpp : 定义控制台应用程序的入口点。

   2:  //

3:

   4:  #include "stdafx.h"

   5:  #include

   6:  #include "windows.h"

   7:  #include

8:

   9:  using namespace std;

10:

  11:  int MaxSum_n3(int *A, int n)//时间复杂度为O(n^3)，最慢的

  12:  {

  13:      int maxsum=-1000;

  14:      int sum;

15:

  16:      for(int i=0;i

  17:      {

  18:          for(int j=i;j

  19:          {

  20:              sum=0;

  21:              for(int k=i; k<=j; k++)

  22:                  sum+=A[k];

  23:              if(sum>maxsum)

  24:                  maxsum=sum;

  25:          }

  26:      }

  27:      return maxsum;

  28:  }

29:

  30:  int MaxSum_n2(int *A, int n)

  31:  {

  32:      int maxsum=-1000;

  33:      int sum;

34:

  35:      for(int i=0; i

  36:      {

  37:          sum=0;

  38:          for(int j=i; j

  39:          {

  40:              sum +=A[j];

  41:              if(sum>maxsum)

  42:              {

  43:                  maxsum=sum;

  44:              }

  45:          }

  46:      }

47:

  48:      return maxsum;

  49:  }

50:

  51:  int MaxSum_nlogn(int *A, int n)

  52:  {

  53:      int maxsum=-1000;

  54:      int sum=0;

  55:      cout<<"未实现分值算法的求最大子段和"<

  56:      return maxsum;

  57:  }

58:

  59:  int Max(int x, int y) //不能写max，似乎和内置函数冲突

  60:  {

  61:      int max;

  62:      max = (x>y)?x:y;

  63:      return max;

  64:  }

65:

  66:  int MaxSum_dp(int *A, int n)

  67:  {

  68:      int nStart[6];  //这个不好，还要提前确定数组大小，要不然就要从堆中分配内存

  69:      int nAll[6];

  70:      nStart[n-1] = A[n-1];

  71:      nAll[n-1] = A[n-1];

  72:      for(int i=n-2; i>=0; i--)

  73:      {

  74:          nStart[i] = Max(A[i],A[i]+nStart[i+1]);

  75:          nAll[i] = Max(nStart[i], nAll[i+1]);

  76:      }

  77:      return nAll[0];

  78:  }

79:

80:

  81:  int MaxSum_dp_saveSpace(int *A, int n)

  82:  {

  83:      int nStart = A[n-1];

  84:      int nAll = A[n-1];

  85:      for(int i=n-2; i>=0; i--)

  86:      {

  87:          nStart = Max(A[i], A[i]+nStart);

  88:          nAll = Max(nStart, nAll);

  89:      }

  90:      return nAll;

  91:  }

92:

  93:  int MaxSum_last(int *A, int n)

  94:  {

  95:      int nStart = A[n-1];

  96:      int nAll = A[n-1];

  97:      for(int i = n-2; i>=0; i--)

  98:      {

  99:          if(nStart <0 )

 100:              nStart = 0;

 101:          nStart += A[i];

 102:          if(nStart > nAll)

 103:              nAll = nStart;

 104:      }

 105:      return nAll;

 106:  }

 107:

 108:

 109:  int MaxSum_July(int *A, int n, int &left, int &right)//最实用版本

 110:  {

 111:      int b,sum;

 112:

 113:      sum=A[0];

 114:      b=0;

 115:      left=0;

 116:      right=0;

 117:

 118:      for(int i=0; i

 119:      {

 120:          if(b<0)

 121:          {

 122:              b=A[i];

 123:              if(b>=0)

 124:                  left=i;

 125:          }

 126:          else

 127:              b+=A[i];

 128:          if(b>sum)

 129:          {

 130:              sum=b;

 131:              right=i;

 132:          }

 133:      }

 134:      if(sum<0)

 135:          left=right;

 136:      return sum;

 137:  }

 138:

 139:

 140:

 141:  int MaxSum_July_goback(int *A, int n, int &left, int &right)//left和right在此无意义

 142:  {

 143:      int b,sum;

 144:

 145:      sum=A[0];

 146:

 147:      b=0;

 148:      left=0;

 149:      right=0;

 150:

 151:      for(int i=0; i

 152:      {

 153:          if(b<0)

 154:          {

 155:              b=A[i];

 156:              if(b>=0)

 157:              {

 158:                  left=i;

 159:              }

 160:          }

 161:          else

 162:              b+=A[i];

 163:          if(b>sum)

 164:          {

 165:              right=i;

 166:              if(right-left

 167:                  sum=b;

 168:          }

 169:      }

 170:      if(sum<0)

 171:          left=right;

 172:      //if(left>n/2)

 173:      //    left=left-n/2;

 174:      //if(right>n/2)

 175:      //    right=right-n/2;

 176:      return sum;

 177:  }

 178:

 179:

 180:  int _tmain(int argc, _TCHAR* argv[])

 181:  {

 182:      int A[6]={0,-2,3,5,-1,2};

 183:      int B[6]={-3,-2,-1,-4,-5,-6};

 184:      int C[12]={3,-4,-5,10,0,0,3,-4,-5,10,0,0};

 185:      long start,end;

 186:      clock_t start2,end2;

 187:

 188:      start=GetTickCount();

 189:      start2=clock();

 190:      cout<
  
   <

 191:      end=GetTickCount();

 192:      end2=clock();

 193:      cout<<"MaxSum_n3 use Time: "<
  
   <

 194:      cout<<"MaxSum_n3 use Time (use clock): "<
  
   <

 195:      cout<

 196:

 197:      start=GetTickCount();

 198:      cout<
  
   <

 199:      end=GetTickCount();

 200:      cout<<"MaxSum_n2 use Time: "<
  
   <

 201:      cout<

 202:

 203:      start=GetTickCount();

 204:      cout<
  
   <

 205:      end=GetTickCount();

 206:      cout<<"MaxSum_nlogn use Time: "<
  
   <

 207:      cout<

 208:

 209:      cout<

 210:      cout<
  
   <

 211:

 212:      cout<

 213:      cout<
  
   <

 214:

 215:      cout<

 216:      cout<
  
   <

 217:

 218:      int left,right;

 219:      left=right=-1;

 220:      //cout<

 221:      cout<<" left = "<
  
   <<
   "  right = "<
   
    <
    
     <
     
      //cout是从右往左，先计算MaxSum_July后，left, right才会被赋值

 222:      cout<
  
   <

 223:

 224:      left=right=-1;

 225:      //cout<

 226:      cout<<" left = "<
  
   <<
   "  right = "<
   
    <
    
     <
     
      //left, right的位置在此无意义

 227:      cout<
  
   <

 228:

 229:      system("pause");return 0;

 230:  }

 231:

程序员的博客