課堂練習4

我們團隊的思路也是同學在課堂上提出的動态規劃問題。這樣就是時空複雜度O（n）。

1.首先把數組的開始值附在一個最優解上。我們用的是，數組array3.

2.當array3[i-1]小于0時,maxsize就為他本身。

3.當array3[i-1]大于0時，maxsize就為array3[i-1]+maxsize；

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

int shuzu(int h,int array2[N])
{
    int i;
    int array3[N];
    array3[0]=array2[0];
    int maxsize=array3[0];
    for(i=1;i<=h;i++)
    {
        if(array3[i-1]>0)
        {
            array3[i]=array3[i-1]+array2[i];
            maxsize=max(maxsize,array3[i-1]);
        }
        else 
        {
            array3[i]=array2[i];

        }
    }
    cout<<"子數組最大為："<<maxsize;
    return 0;

}

int main()
{
    int i,j;
    cout<<"請輸入數組大小：(1-10)"<<endl;
    cin>>j;

    int array1[N];

    cout<<"請輸入"<<j<<"個數："<<endl;

    for(i=0;i<j;i++)
    {
        cin>>array1[i];
    }
    shuzu(j,array1);
    
    return 0;
}      

組員位址唐野野：http://www.cnblogs.com/tyyhph/