返回一個整數陣列中最大子陣列的和 C語言
1、題目:返回一個整數陣列中最大子陣列的和。
2、要求：
要求程式必須能處理1000 個元素；
每個元素是int32 型別的；
輸入一個整形陣列，數組裡有正數也有負數。
陣列中連續的一個或多個整陣列成一個子陣列，每個子陣列都有一個和。
求所有子陣列的和的最大值。要求時間複雜度為O(n)。
3、設計思路：
將陣列大小定義為1000，對於每個元素定義為int32型別，將求和函式設定為int 型別，這樣可以方便觀測資料的溢位，讓陣列元素可以超出範圍。
4.程式程式碼：
#include<iostream>
#include<time.h>
#include<conio.h>
#define N 1000
using namespace std;
void RandIn(int IntNum,int A[]) //隨機生成陣列
{
cout<<"整數內容"<<endl;
for(int i=0;i<IntNum;i++)
{
A[i]=rand()-rand();
cout<<A[i];
if(i%15==4)
cout<<endl;
else
cout<<'\t';
}
}
void SelMax(int IntNum,int A[],auto &sum)
{
int buffer=0;
int count1=0; //求和的數值個數
int count2=0; //進行的運算次數
for(int j=0;j<=IntNum;j++)
{
if(j==IntNum)
{
j=0;
}
buffer+=A[j];
count1++;
count2++;
if(buffer<0)
{
buffer=0;
count1=0;
}
if(sum<buffer)//sum始終記錄下存在的最大和
{
sum=buffer;
}
{
break;
}
}
}
void main()
{
int IntNum;
int A[N];
int q=0;
while(q==0)
{
auto sum=0;
srand((unsigned)time(NULL));
cout<<"請輸入陣列元素的個數:";
cin>>IntNum;
RandIn(IntNum,A);
SelMax(IntNum,A,sum);
cout<<endl;
cout<<sum<<endl;
cout<<"是否繼續測試(輸入0則繼續否則停止)";
cin>>q;
system("cls");
}
}
5.執行結果
無溢位時：
溢位時：對程式碼進行改動，在求和程式碼函式中*4294967296（也就是2的32次方） 這樣在執行程式之後就會溢位，截圖如下：
6.實驗感想：這次實驗讓我明白了實驗程式碼簡練的重要性，演算法優化的重要性，這樣可以節省運算時間，所以這次試驗我收穫很多，下次
實驗我會更加用心，學習到更多知識，讓我更上一層樓。
7.小組相片：
