记分治法求最大子序列正确性的一次不完全证明

依旧现贴出程序代码再进行分析：

1:  #include <stdio.h>

2:  #include <stdlib.h>

3:

4:  int sc=0;

5:  int max3(int a,int b, int c)

6:  {

7:      sc++;

8:      if(a>b)

9:      {

10:          return a>c?a:c;

11:      }

12:      else

13:      {

14:          return b>c?b:c;

15:      }

16:  }

17:

18:  int max_sub_sum(const int v[], int left, int right)

19:  {

20:      int center;

21:      int maxLeftHalfSum;

22:      int maxRightHalfSum;

23:      int leftHalfWithRightBorderSum;

24:      int rightHalfWithLeftBorderSum;

25:      int maxLeftHalfWithRightBorderSum;

26:      int maxRightHalfWithLeftBorderSum;

27:      int i;

28:

29:      if(left==right)

30:      {

31:          return v[left]>0?v[left]:0;

32:      }

33:      center=(left+right)/2;

34:

35:      maxLeftHalfWithRightBorderSum=leftHalfWithRightBorderSum=

36:      maxRightHalfWithLeftBorderSum=rightHalfWithLeftBorderSum=0;

37:      for(i=center;i>=left;i--)

38:      {

39:          leftHalfWithRightBorderSum+=v[i];

40:          if(leftHalfWithRightBorderSum>maxLeftHalfWithRightBorderSum)

41:          {

42:              maxLeftHalfWithRightBorderSum=leftHalfWithRightBorderSum;

43:          }

44:      }

45:

46:      for(i=center+1;i<=right;i++)

47:      {

48:          rightHalfWithLeftBorderSum+=v[i];

49:          if(rightHalfWithLeftBorderSum>maxRightHalfWithLeftBorderSum)

50:          {

51:              maxRightHalfWithLeftBorderSum=rightHalfWithLeftBorderSum;

52:          }

53:      }

54:

55:      return max3(max_sub_sum(v,left,center),max_sub_sum(v,center+1,right),

56:                  maxLeftHalfWithRightBorderSum+maxRightHalfWithLeftBorderSum);

57:  }

58:

59:  int main()

60:  {

61:      int v[]={1,-1,2,-2,1,-1,2,-2,1,-1,2,-2,1,-1,2,-2,1,-1,2,-2,1,-1,2,-2,1,-1,2,-2,1,-1,2,-2};

62:      int r=max_sub_sum(v,0,31);

63:      printf("the max sub sum is %d in step %d",r,sc);

64:      return 0;

65:  }

如下为证明分治法求解该问题的有效性，随手写来，好久没做证明题了，如有错误，还望不令赐教

原文链接: https://www.cnblogs.com/dancewithautomation/archive/2012/06/17/2552566.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍