要求时间复杂度为O(n)的求两个位置之间最大值的算法

问题描述：

把一串数（32位int型）放到Num中，求begin和end位置使得begin与end之间的是数字和最大，要求时间复杂度是O（n）。
注：不可以先排序，这串数字的位置不能改变。
最好有源码，思路也可以。

答

#include
#include

int getmax(int first, int second)
{
return first > second ? first : second;
}

int main()
{
int start_index = 0, end_index = 0;
int sum_max = 0, result = 0;

    int index = 0;

    int data[] = {1, 3, -5, 0, 6, -4, 9, 12, -1};

    int count = sizeof(data)/sizeof(int);

    for(index = 0; index < count; index++)
    {
            sum_max = getmax(0, sum_max) + data[index];
            if(data[index] >= sum_max)
            {
                    start_index = index;
            }
            result = getmax(result, sum_max);
            if(result == sum_max)
            {
                    end_index = index;
            }
    }
    printf("min section [%d, %d],sum : %d\n", start_index, end_index, result);
    return 0;

}

答

设sum[n]是以n为end的最大和
状态转移方程：sum[n]=max(0,sum[n-1])+a[n] 复杂度为O(n)

要求时间复杂度为O(n)的求两个位置之间最大值的算法

相关推荐