本次作业，我使用了两种方法，分别为枚举法和动态规划法，下面是源程序和测试结果截图

测试数据1:1 2 -3 4，最大和为4

测试数据2（全为负数）：-1 -2 -3 -4 最大和-1

方法一：

代码如下

#include
     
      #include
      
       int main(){    int a[100],i,j,x,sum=0,n,max=-9999;    scanf("%d",&n);    for(i=0;i
       
        =i;j--)      {      sum=0;      for(x=i;x<=j;x++)      sum=sum+a[x];             if (max
       
      
     

 这是一种暴力算法

算法将所有可能的值全部计算，通过与max值相比较

大于max的sum将max赋值为sum

小于max的sum跳过

这种方法的好处是想法简单，但是时间复杂度高，需要长时间来执行。

通过计算，该算法的时间复杂度为O（n^3）

 

考虑到算法1的时间复杂度问题，我又写了第二个算法，该算法使用动态规划的方法进行，时间复杂度低

#include 
     
      int main(){  int dp[100]={0};  int a[100]={0};  int num,max;  int i,j,k;  scanf("%d",&num);  max=-9999;  for (i=1;i<=num;i++)  {    scanf("%d",&a[i]);    dp[i]=a[i]+dp[i-1];    if (max
     

 

 动态规划的时间复杂度经过计算仅为O（n），较之暴力枚举法快了非常多