MAXIMUM SUBSEQUENCE SUM PROBLEM:

  1. #include <stdio.h>
  2. //算法一，运行时间为O(N3)
  3. int MaxSubsequenceSum(const int A[], int N)
  4. {
  5.     int ThisSum, MaxSum = 0, i, j, k;
  6.     for (i = 0; i < N; i++)
  7.         for (j = i; j < N; j++)
  8.         {
  9.             ThisSum = 0;
  10.             for (k = i; k <= j; k++)
  11.                 ThisSum += A[k];
  12.             if (ThisSum > MaxSum)
  13.                 MaxSum = ThisSum;
  14.         }
  15.     return MaxSum;
  16. }
  17. //算法二，运行时间为（N2)
  18. int MaxSubSequenceSum(const int A[], int N)
  19. {
  20.     int ThisSum, MaxSum = 0, i, j;
  21.     for (i = 0; i < N; i++)
  22.     {
  23.         ThisSum = 0;
  24.         for (j = i; j < N; j++)
  25.         {
  26.             ThisSum += A[j];
  27.             if (ThisSum > MaxSum)
  28.                 MaxSum = ThisSum;
  29.         }
  30.     }
  31.     return MaxSum;
  32. }
  33. //算法三，运行时间为O（Nlog(N))
  34. int Max3(int a, int b, int c)
  35. {
  36.     if (a > b)
  37.         if (a > c)
  38.             return a;
  39.         else
  40.             return c;
  41.     else
  42.         if (b > c)
  43.             return b;
  44.         else
  45.             return c;
  46. }
  47. static int MaxSubSum(const int A[], int Left, int Right)
  48. {
  49.     int MaxLeftSum, MaxRightSum;
  50.     int MaxLeftBorderSum = 0, MaxRightBorderSum = 0;
  51.     int LeftBorderSum = 0, RightBorderSum = 0;
  52.     int Center, i;
  53.     if (Left == Right) /*Base Case*/
  54.         if (A[Left] > 0)
  55.             return A[Left];
  56.         else
  57.             return 0;
  58.     Center = (Left + Right) / 2;
  59.     MaxLeftSum = MaxSubSum(A, Left, Center);
  60.     MaxRightSum = MaxSubSum(A, Center + 1, Right);
  61.     for (i = Center; i >= Left; i--)
  62.     {
  63.         LeftBorderSum += A[i];
  64.         if (LeftBorderSum > MaxLeftBorderSum)
  65.             MaxLeftBorderSum = LeftBorderSum;
  66.     }
  67.     for (i = Center + 1; i <= Right; i++)
  68.     {
  69.         RightBorderSum += A[i];
  70.         if (RightBorderSum > MaxRightBorderSum)
  71.             MaxRightBorderSum = RightBorderSum;
  72.     }
  73.     return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
  74. }
  75. //算法四，运行时间为O（N)
  76. int MaxSubSequence(const int A[], int N)
  77. {
  78.     int ThisSum = 0, MaxSum = 0, j;
  79.     for (j = 0; j < N; j++)
  80.     {
  81.         ThisSum += A[j];
  82.         if (ThisSum > MaxSum)
  83.             MaxSum = ThisSum;
  84.         else if (ThisSum < 0)
  85.             ThisSum = 0;
  86.     }
  87.     return MaxSum;
  88. }
  89. int main()
  90. {
  91.     int N, A[100], i;
  92.     scanf_s("%d", &N);
  93.     for (i = 0; i < N; i++)
  94.         scanf_s("%d", &A[i]);
  95.     int Max;
  96.     Max = MaxSubsequenceSum(A, N);//随便调取一个
  97.     printf("%d", Max);
  98.     return 0;
  99. }