整数数组的最大子数组

//注：本小队有三人，分别为王友军，黄瑞玻，白宇乾；因本班级人数为奇数，故如此

本次作业为返回整数数组中最大的子数组，应用c++编写，在visual c++ 2010 平台执行。

在编写过程中学会以下知识：

1. 应用 int n；int *p=new int[n]；开辟动态储存空间。满足输入动态数组的要求。
2. 应用switch语句实现程序功能的多元化。
3. 使用如下代码判断最大子数组之和。 for(int i=0;i<n;i++)
    {
     cin>>p[i];
    }
    int sum=p[0];
      int max_sum=p[0];
      for(int i=1;i<n;i++)
      {   
          if(sum>0)    //是否为正数
          { 
              sum=sum+p[i];  //是正数，做和。
             if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
               { 
                   max_sum=sum;
                   end=i;
               }
          }
          else 
          { 
              sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
                 if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
                 {    
                    max_sum=sum;
                    star=i;
                    end=i;
                 }
          }
      }
      cout<<"最大子数组位置为第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
      cout<<"最大子数组和为"<<max_sum<<endl;
4. 应用p[i]=rand()输入随机数组。如果不再加任何条件时数组元素范围为零到32767 （2^16-1），其计算原理为：y＝ax＋b（mod n）其中，n一般是一个很大的素数，几万。 
   a也是大素数。而且a，b，n都是常数。所以rand的产生决定于x， 
   他被称为seed。 
   每一个seed都是上一次产生的y的函数。这样，如果直接取seed＝y的话， 
   虽然产生的rand之间相关性甚小，但只要知道某个y，就能推知以后的rand。 
   为避免这种情况，一般取seed为y和当时计算机的时间的函数，如seed＝y＋t
   
   比如VC中对于rand()函数是如下实现的. 
   int __cdecl rand (void) 
   { 
   return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff); 
   }
5. 如果想用rand函数输出负数时，可以这样应用：p[i]=-rand()%4000+2000;

    1 #include<iostream>
    2 #include<ctime>
    3 using namespace std;
    4 int main()
    5 {
    6     cout<<"数1601-2 20163980 \n黄瑞波"<<endl;;
    7     int m,n=0,star=0,end=0;
    8     cout<<"1.手动输入数组。\n2.随机生成数组。请选择功能：";//选择自己输入或者随机生成
    9     cin>>m;
   10     switch(m)
   11     {
   12         case 1:{
   13         int *p=new int[n];//开辟为n的存储空间
   14     cout<<"请输入数组的长度：";
   15     cin>>n;
   16     if(n<0)
   17     {
   18     cout<<"输入的数组长度有误，请重新输入！"<<endl;//判断数据有效性
   19     return 0;
   20     }
   21     cout<<"输入一个"<<n<<"维整型数组:";
   22     //以下算法代码参考与网络。
   23     for(int i=0;i<n;i++)
   24     {
   25         cin>>p[i];
   26     }
   27     int sum=p[0];
   28    int max_sum=p[0];
   29    for(int i=1;i<n;i++)
   30    {   
   31        if(sum>0)    //是否为正数
   32        { 
   33            sum=sum+p[i];  //是正数，做和。
   34           if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
   35             { 
   36                 max_sum=sum;
   37                 end=i;
   38             }
   39        }
   40        else 
   41        { 
   42            sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
   43               if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
   44               {    
   45                  max_sum=sum;
   46                  star=i;
   47                  end=i;
   48               }
   49        }
   50    }
   51    cout<<"最大子数组位置为第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
   52    cout<<"最大子数组和为"<<max_sum<<endl;
   53 };break;
   54         case 2:
   55             {
   56                 int *p=new int[n];
   57                 cout<<"请输入数组的长度：";
   58         cin>>n;
   59         if(n<0)
   60         {
   61         cout<<"输入的数组长度有误，请重新输入！"<<endl;
   62         return 0;
   63         }cout<<"随机数组为：";
   64         for(int i=0;i<n;i++)
   65     {
   66         p[i]=-rand()%4000+2000;
   67         cout<<p[i]<<" ";
   68     }
   69         cout<<endl;
   70         int sum=p[0];
   71    int max_sum=p[0];
   72    for(int i=1;i<n;i++)
   73    {   
   74        if(sum>0)    //判断是否为正数
   75        { 
   76            sum=sum+p[i];  //是正数，做和。
   77           if(sum>max_sum) // 并判断是否为最大，是让其赋值给max_sum。
   78             { 
   79                 max_sum=sum;
   80                 end=i;
   81             }
   82        }
   83        else 
   84        { 
   85            sum=p[i];  //是负数，将第i+1个数的值赋值给和值sum
   86               if(sum>max_sum)//并判断是否为最大，是让其赋值给max_sum。
   87               {    
   88                  max_sum=sum;
   89                  star=i;
   90                  end=i;
   91               }
   92        }
   93    }
   94    cout<<"最大子数组位置为:第"<<star+1<<"个到第"<<end+1<<"个"<<endl;
   95    cout<<"最大子数组和为:"<<max_sum<<endl;
   96             };break;
   97     }
   98       return 0;
   99 }

   运行结果截图为：

   

    

    

    

   

整数数组的最大子数组

原文：https://www.cnblogs.com/Kirito-math/p/9787955.html