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

The 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 algorithm  1
    unsigned int utimecost = GetTickCount();
    int result = maxsubsum1(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    // adopt algorithm  2
    utimecost = GetTickCount();
    result = maxsubsum2(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    free(ptr);

    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， for
， 时间
， The
最大子序列
，以便于您获取更多的相关知识。