C求最长子序列和
法一：O（n^3）
- #include <stdio.h>
- #include <stdlib.h>
- int sub_Sum(int a[], int left, int right)
- {
- int i, temp_sum = 0;
- for(i = left; i <= right; i++)
- {
- temp_sum += a[i];
- }
- return temp_sum;
- }
- int main()
- {
- int i, j, k, len;
- int max_sum = 0, cur_sum = 0;
- printf(“Please input the length of the sequence: \n”);
- scanf(“%d\n”, &len);
- int *a = (int *)malloc(len * sizeof(i));
- for(i = 0; i < len; i++)
- {
- scanf(“%d”, &a[i]);
- }
- for(i = 0; i < len; i++)
- {
- for(j = i; j < len; j++)
- {
- for(k = i; k <= j; k++)
- {
- cur_sum += a[k];
- }
- if(cur_sum > max_sum)
- max_sum = cur_sum;
- cur_sum = 0;
- }
- }
- printf(“Max sum is : %d\n”, max_sum);
- max_sum = 0;
- for(i = 0; i < len; i++)
- {
- for(j = i; j < len; j++)
- {
- cur_sum = sub_Sum(a, i, j);
- if(cur_sum > max_sum)
- max_sum = cur_sum;
- cur_sum = 0;
- }
- }
- printf(“Max sum is : %d\n”, max_sum);
- free(a);
- return 0;
- }
法二：O(n^2)
- #include <stdio.h>
- #include <stdlib.h>
- int main()
- {
- int i, j, len;
- int cur_sum = 0, max_sum = 0;
- printf(“Please input the length of the sequence : \n”);
- scanf(“%d\n”, &len);
- int *a = (int *)malloc(len * sizeof(int));
- for(i = 0; i < len; i++)
- {
- scanf(“%d”, &a[i]);
- }
- for(i = 0; i < len; i++)
- {
- //计算一次以i开始的最大和值
- for(j = i; j < len; j++)
- {
- cur_sum += a[j];
- if(cur_sum > max_sum)
- {
- max_sum = cur_sum;
- }
- }
- cur_sum = 0;
- }
- printf(“The max sum is: %d\n”, max_sum);
- free(a);
- return 0;
- }
