By

文章目录
  1. 1. 问题描述

问题描述

输入是具有n个浮点数的向量，输出是输入向量的任何连续子向量中的最大和。
最简单的方法是对所有满足i,j在0到n的的整数进行迭代，对每个整数对，程序计算data[i…j]的和，并检验总和是否大于迄今为止最大的总和。
这种方法的复杂度为o(n^3),当n为100000时，要运行10天时间。
那么为了优化这种代码，使用下面三种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
float maxsum1(int l,int u)//时间复杂度o(n^2)
{
    int sumarray[MAX_LENGTH];
    sumarray[0] = data[0];
    for(int i =l;i<=u;i++)
    {
        sumarray[i] = sumarray[i-1]+data[i];
    }
    int sum = 0;
    int maxsum = 0;
    for(int i = l;i<=u;i++)
    {
        for(int j=l;j<=u;j++)
        {
            sum = sumarray[j] - sumarray[i-1];
            maxsum = max(sum,maxsum);
        }
    }
    return maxsum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
float maxsum(int l,int u)//时间复杂度o(nlogn)
{
    if(l>u)
        return 0;
    if(l==u)
        return max(0,data[l]);
    int m =(l+u)/2;
    int lmax = 0,rmax =0, sum =0;
    int i;
    for(i=m;i>=l;i--)
    {
        sum = sum +data[i];
        lmax = max(lmax,sum);
    }
    sum = 0;
    for(i=m+1;i<=u;i++)
    {
        sum = sum+data[i];
        rmax = max(rmax,sum);
    }
    int temp =max(maxsum(l,m),maxsum(m+1,u));
    return max(temp,lmax+rmax);
}
1
2
3
4
5
6
7
8
9
10
11
float maxsum2(int l,int u)//时间复杂度o(n)
{
    int maxsum = 0;
    int maxendinghere =0;
    for(int i =l;i<=u;i++)
    {
        maxendinghere = max(maxendinghere+data[i],0);
        maxsum = max(maxsum,maxendinghere);
    }
    return maxsum;
}
文章目录
  1. 1. 问题描述