小sugar呀____最大子數組問題（算法導論）

DAY2

題目：要求一個數組連續下标和的最大值，數組的元素可正、可負、可為零，例如-2，5，3，-6，4，-8，6将傳回8。

參考來源：三種算法求解一個數組的子數組最大和 - Fangzhen - 部落格園

http://www.cnblogs.com/xkfz007/archive/2012/05/17/2506299.html

算法導論——最大子數組問題 - binta - SegmentFault

https://segmentfault.com/a/1190000000733277

1.暴力求解法：

時間複雜度為O(n2)

```
#include<stdio.h>
#include<limits.h>
#include<time.h>
int maxsubset(int *a,int t)
{
    int i,j,k,summax=INT_MIN;
    for(i=; i<t; i++)
        for(j=i; j<t; j++)
        {
            int temp=;
            for(k=i; k<=j; k++)
                temp+=a[k];
            if(temp>summax) summax=temp;
        }
    return summax;
}
int main()
{
    int a[]= {,-,,,-,,-,-,,,-,,};
    printf("暴力求解法所得為%d\n",maxsubset(a,));
           printf("所用時間為%f\n",(double)clock() / CLOCKS_PER_SEC);
           return ;
}
           

運作結果如圖所示：

2.分治算法

時間複雜度O(nlogn)

#include<stdio.h>
#include<time.h>
#include<limits.h>
int cross_middle(int *a,int l,int m,int r)
{
    int i,sum=,l_max=INT_MIN,r_max=INT_MIN;
    for(i=m; i>=l; i--) //向左搜尋
    {
        sum+=a[i];
        if(sum>l_max) l_max=sum;
    }
    sum=;
    for(i=m+; i<=r; i++) //向右搜尋
    {
        sum+=a[i];
        if(sum>r_max) r_max=sum;
    }
    return (l_max+r_max);
}
int maxsubset(int *a,int l,int r)
{
    if(l==r) return a[l];
    int l_max,r_max,c_max,m=(l+r)/;
    l_max=maxsubset(a,l,m);
    r_max=maxsubset(a,m+,r);
    c_max=cross_middle(a,l,m,r);
    if(l_max>=r_max&&l_max>=c_max) return l_max;
    else if(r_max>=l_max&&r_max>=c_max) return r_max;
    else return c_max;
}
int main()
{
    int a[]= {,-,,,-,,-,-,,,-,,};
    printf("分治算法所得為%d\n",maxsubset(a,,));
    printf("所用時間為%f\n",(double)clock() / CLOCKS_PER_SEC);
    return ;
}
           

運作結果如圖所示：

3.動态規劃（線性時間實作）

算法時間複雜度O(n)

#include<stdio.h>
#include<time.h>
#include<limits.h>
int maxsbuset(int *a,int l,int r)
{
    int i,temp=,summax=INT_MIN;
    for(i=l; i<=r; i++)
    {
        temp+=a[i];
        if(temp>summax) summax=temp;
        if(temp<) temp=;
    }
    return summax;
}
int main()
{
    int a[]= {,-,,,-,,-,-,,,-,,};
    printf("線性規劃所得為%d\n",maxsbuset(a,,));
    printf("所用時間為%f\n",(double)clock() / CLOCKS_PER_SEC);
    return ;
}
           

“`

運作結果如圖所示