C求最长子序列和

法一:O(n^3)

[cpp] 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int sub_Sum(int a[], int left, int right)
  4. {
  5.     int i, temp_sum = 0;
  6.     for(i = left; i <= right; i++)
  7.     {
  8.         temp_sum += a[i];
  9.     }
  10.     return temp_sum;
  11. }
  12. int main()
  13. {
  14.     int i, j, k, len;
  15.     int max_sum = 0, cur_sum = 0;
  16.     printf(“Please input the length of the sequence: \n”);
  17.     scanf(“%d\n”, &len);
  18.     int *a = (int *)malloc(len * sizeof(i));
  19.     for(i = 0; i < len; i++)
  20.     {
  21.         scanf(“%d”, &a[i]);
  22.     }
  23.     for(i = 0; i < len; i++)
  24.     {
  25.         for(j = i; j < len; j++)
  26.         {
  27.             for(k = i; k <= j; k++)
  28.             {
  29.                 cur_sum += a[k];
  30.             }
  31.             if(cur_sum > max_sum)
  32.                 max_sum = cur_sum;
  33.             cur_sum = 0;
  34.         }
  35.     }
  36.     printf(“Max sum is : %d\n”, max_sum);
  37.    max_sum = 0;
  38.     for(i = 0; i < len; i++)
  39.     {
  40.         for(j = i; j < len; j++)
  41.         {
  42.             cur_sum = sub_Sum(a, i, j);
  43.             if(cur_sum > max_sum)
  44.                 max_sum = cur_sum;
  45.             cur_sum = 0;
  46.         }
  47.     }
  48.     printf(“Max sum is : %d\n”, max_sum);
  49.     free(a);
  50.     return 0;
  51. }

 

法二:O(n^2)

 

[cpp] 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main()
  4. {
  5.     int i, j, len;
  6.     int cur_sum = 0, max_sum = 0;
  7.     printf(“Please input the length of the sequence : \n”);
  8.     scanf(“%d\n”, &len);
  9.     int *a = (int *)malloc(len * sizeof(int));
  10.     for(i = 0; i < len; i++)
  11.     {
  12.         scanf(“%d”, &a[i]);
  13.     }
  14.     for(i = 0; i < len; i++)
  15.     {
  16.         //计算一次以i开始的最大和值
  17.         for(j = i; j < len; j++)
  18.         {
  19.             cur_sum += a[j];
  20.             if(cur_sum > max_sum)
  21.             {
  22.                 max_sum = cur_sum;
  23.             }
  24.         }
  25.         cur_sum = 0;
  26.     }
  27.     printf(“The max sum is: %d\n”, max_sum);
  28.     free(a);
  29.     return 0;
  30. }

标签