課堂練習2

課堂練習2

1.設計思想

    第一次求子數組最大和的程式存儲和的時候用的二維數組不能夠實作時間複雜度為O(n)，然後也沒什麼新的思路，就從網上搜了一種算法。

    該算法是構造一個函數來傳回子數組的最大和，目前面的幾個數，加起來後，b<0後， 把b重新指派，置為下一個元素，b=a[i]。 當b>sum，則更新sum=b; 若b<sum，則sum保持原值，不更新。

2.源程式

#include <iostream>
using namespace std;
#define N 15

int max(int *a)
{
    int sum=0,b=0;
    for(int i=0;i<N;i++)
    {
         if(b<0)
        {
             b=a[i];
        }
        else
        {
            b+=a[i];
        }
        if(sum<b)
        {
            sum=b;
        }
    }
    return sum;
}


void main()
{
    int a[N];
    cout<<"生成的數組為:";
    for(int i=0;i<N;i++) //生成數組裡的随機數
   {
        a[i]=rand()%100-50;
        cout<<a[i]<<" ";
    }
    cout<<endl;

    cout<<"最大數組的和為:"<<max(a)<<endl;

}      

3.結果截圖

4.總結

  很遺憾的最後沒有輸出子數組，對于子數組的輸出沒有什麼思想，也從中學到了一種新的算法，希望再經過思考能夠将這個問題解決的更好。

5.工作照

陳傑：主要進行博文的總結等

孟祥娟：主要負責程式的編寫和運作測試