最大连续子序列的算法优越性反映

题目比较简单，就是最大连续子序列，比如说[7,-6,-2,8]中最大连续子序列就是[8]
然而问题来了，我用C语言写了一个常规的三个for循环（时间复杂度O(n^3)）还有动态规划的方法（时间复杂度O(n)）,但是用Devcpp跑出来的时间居然差不多
我用python的随机数做测试，结果出现要么结果都跑不出来，要么运行时间没有差别
希望有奆佬帮我看一下原因，怎么让程序反映算法的优越性
以下附上代码C代码

#include<stdio.h>
#define N 1000
int L[N];
int way1(){
    int ans=-99999;
    for(int i=0;i<N;i++){
        scanf("%d",&L[i]);
    }
    printf("Try Way1\n");
    for(int i=1;i<=N;i++){
        for(int j=0;j<N-i+1;j++){
            int sum=0;
            for(int k=j;k<j+i;k++){
                sum+=L[k];
            }
            if (sum>ans){
                ans=sum;
            }
        }
    }
    return ans;
}
int way2(){
    int ans=-99999;
    for(int i=0;i<N;i++){
        scanf("%d",&L[i]);
    }
    printf("Try Way2\n");
    int maxs[N];
    for(int i=0;i<N;i++){
        maxs[i]=L[i];
    }
    for(int i=N-2;i>=0;i--){
        if(maxs[i+1]+L[i]>maxs[i])
            maxs[i]=maxs[i+1]+L[i];
    }
    for(int i=0;i<N;i++){
        if(maxs[i]>ans){
            ans=maxs[i];
        }
    }
    return ans;
}
int main(){
    printf("%d\n",way1());
    printf("%d\n",way2());
    return 0;
}

以下附上python随机数代码

import random
n=1000
a=[0]*n
s=""
for i in range(n):
    a[i]=random.randint(-100,100)
    s+=str(a[i])+" "
print(s)

【以下回答由 GPT 生成】

首先，分析一下你提供的两个算法的时间复杂度：

• way1算法使用三个for循环，其中第一个for循环会执行N次，第二个for循环会执行(N-i+1)次，第三个for循环会执行i次。所以总的时间复杂度为O(N^3)。
• way2算法使用两个for循环，其中第一个for循环会执行N次，第二个for循环会执行N次。所以总的时间复杂度为O(N)。

在分析完算法的时间复杂度后，我们来看一下给出的C代码。

首先，我发现你在way1和way2函数中都将随机数存储在了全局数组L中，而且数组L的大小为1000，这个大小应该与你生成随机数的个数相一致，否则会导致程序出错。在你的Python代码中，你生成了1000个随机数，所以C代码中的数组大小应该也为1000。

另外，你在每个函数中都使用了scanf函数来读取输入的随机数，但是在你提供的代码中，并没有提供输入的过程，所以在测试代码时可能会出现错误。你可以将读取输入的部分放在main函数中，然后将随机数通过参数传递给way1和way2函数。

接下来，我们来看一下如何优化算法来使程序的运行时间更好地反映算法的优越性。

对于最大连续子序列问题，可以使用动态规划的思想来解决。但是你提供的way2算法已经是动态规划的算法了，所以在这里我们可以通过优化动态规划的实现方式来提高算法的效率。

当前的way2算法中使用了一个数组maxs来存储当前位置的局部最优解，然后再遍历这个数组来找到全局最优解。这个过程中会使用到N个存储空间，但实际上我们只需要存储前一个位置的最优解和当前位置的最优解即可。

所以我们可以将maxs数组改为只存储两个元素，分别表示前一个位置和当前位置的最优解。然后我们遍历数组，每次更新这两个元素的值，同时记录最大的最优解。这样就可以减少空间复杂度。

下面是修改后的C代码：

#include<stdio.h>
#define N 1000

int way1(int* L){
    int ans = -99999;
    for(int i=1;i<=N;i++){
        for(int j=0;j<N-i+1;j++){
            int sum=0;
            for(int k=j;k<j+i;k++){
                sum+=L[k];
            }
            if (sum>ans){
                ans=sum;
            }
        }
    }
    return ans;
}

int way2(int* L){
    int ans = -99999;
    int prev_max = L[0];
    int curr_max = L[0];

    for(int i=1;i<N;i++){
        if(curr_max + L[i] > L[i]){
            curr_max = curr_max + L[i];
        } else {
            curr_max = L[i];
        }

        if(curr_max > ans){
            ans = curr_max;
        }

        if(prev_max < curr_max){
            prev_max = curr_max;
        }
    }

    return ans;
}

int main(){
    int L[N];
    for(int i=0;i<N;i++){
        scanf("%d",&L[i]);
    }

    printf("%d\n",way1(L));
    printf("%d\n",way2(L));
    return 0;
}

这样修改后的程序会更加高效，因为减少了存储空间的使用。

另外，你在测试时可以将样本数量增加到更大的规模，比如10000，这样可以更明显地体现出两种算法的运行时间差异。而且在进行多次测试的时候，需要确保每次测试的输入都是相同的，这样才能比较运行时间的差异。

希望以上的解答能对你有所帮助，如果还有任何问题，请随时追问。