算法研究：最大子序列求和问题的解决方案

算法研究：最大子序列求和问题的解决方案2013-08-20The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers （containing at least one positive number） which has the largest sum. For example, for the sequence of values ？2, 1, ？3, 4, ？1, 2, 1, ？5, 4; the contiguous subarray with the largest sum is 4, ？1, 2, 1, with sum 6. --from wiki

下面我们分析四种算法的时间性能,由于运行时间相差较大，我们分成两组进行对比：

环境：ubuntu 12.04

时间单位：ms

时间性能：presume that the input is preread

第一组：输入数据元素个数2000

/*************************************************************************> File Name: algorithm1.c> Author: Simba> Mail: dameng34@163.com> Created Time: 2012年12月24日 星期一 22时41分56秒 ************************************************************************/#include<stdio.h>#include<stdlib.h>#include<time.h>#include<sys/time.h>int maxsubsum1（const int a[], int n）{int thissum, maxsum, i, j, k;maxsum = 0;for （i = 0; i < n; i++）{for （j = i; j < n; j++）{thissum = 0;for （k = i; k <= j; k++）thissum += a[k];if （thissum > maxsum）maxsum = thissum;}}return maxsum;}int maxsubsum2（const int a[], int n）{int thissum, maxsum, i, j;maxsum = 0;for （i = 0; i < n; i++）{thissum = 0;for （j = i; j < n; j++）{thissum += a[j];if （thissum > maxsum）maxsum = thissum;}}return maxsum;}long GetTickCount（void）{struct timeval tv;gettimeofday（&tv, NULL）;return （tv.tv_sec * 1000 + tv.tv_usec / 1000）;}int main（void）{int i, n = 2000;int *ptr = malloc（sizeof（int） * n）;srand（time（NULL））;for （i = 0; i < n; i++）ptr[i] = rand（） % 50 - 25;// adopt algorithm1unsigned int utimecost = GetTickCount（）;int result = maxsubsum1（ptr, n）;utimecost = GetTickCount（） - utimecost;printf（"max subsequence sum is %d, time cost %d
", result, utimecost）;// adopt algorithm2utimecost = GetTickCount（）;result = maxsubsum2（ptr, n）;utimecost = GetTickCount（） - utimecost;printf（"max subsequence sum is %d, time cost %d
", result, utimecost）;free（ptr）;return 0;}