算法：最大子数组own

转载标明出处：http://i.cnblogs.com/EditPosts.aspx?postid=4726782&update=1

暴力法:

 1 // maxValue.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 int findMax(int *a,int low,int high,int &sub_left,int &sub_right,int &sub_sum)
10 {
11     if (low==high)
12     {
13         if(a[low]>0)
14         {
15             sub_left=low;
16             sub_right=high;
17             sub_sum=a[low];
18         }
19         else sub_sum=0;
20     }
21 
22     else
23     {
24         for(int i=0;i<=high;i++)
25         {
26             int tempSum=0;
27             for (int j=i;j<=high;j++)
28             {
29                 tempSum+=a[j];
30                 if (tempSum>sub_sum)
31                 {
32                     sub_sum=tempSum;
33                     sub_left=i;
34                     sub_right=j;
35                 }
36             }
37         }
38     }
39     return 0;
40 }
41 
42 int _tmain(int argc, _TCHAR* argv[])
43 {
44     int sub_left=0;
45     int sub_right=0;
46     int sub_sum=0;
47     int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
48     findMax(a,0,15,sub_left,sub_right,sub_sum);
49     cout<<sub_left<<" "<<sub_right<<" "<<sub_sum<<endl;
50     system("pause");
51     return 0;
52 }

View Code

时间复杂度：O(n*n);

分治法:

// maxSubArray.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int Find_Max_cross_subArray(int *a,int low,int middle,int high,int &max_left,int &max_right,int &max_value)
{
    int left_sum=-100;
    int sum=0;
    for (int i=middle;i>=low;i--)
    {
        sum+=a[i];
        if (sum>left_sum)
        {
            left_sum=sum;
            max_left=i;
        }
    }

    int right_sum=-100;
    sum=0;
    for (int j=middle+1;j<=high;j++)
    {
        sum+=a[j];
        if (sum>right_sum)
        {
            right_sum=sum;
            max_right=j;
        }
    }
    max_value=left_sum+right_sum;
    return 0;

}

int Find_Max_subArray(int *a,int low,int high,int &max_left,int &max_right,int &max_vlaue)
{
    if (low==high)
    {
        if (a[low]>0)
        {
            max_vlaue=a[low];
            max_left=low;
            max_right=high;
        }
        else max_vlaue=0;
    }
    else
    {
        int middle=(low+high)/2;
        int tem_left_low;
        int tem_left_high;
        int tem_left_sum;
        Find_Max_subArray(a,low,middle,tem_left_low,tem_left_high,tem_left_sum);
        
        int tem_right_low;
        int tem_right_high;
        int tem_right_sum;
        Find_Max_subArray(a,middle+1,high,tem_right_low,tem_right_high,tem_right_sum);

        int tem_cross_low;
        int tem_cross_high;
        int tem_cross_sum;
        Find_Max_cross_subArray(a,low,middle,high,tem_cross_low,tem_cross_high,tem_cross_sum);

        if (tem_left_sum>=tem_right_sum&&tem_left_sum>=tem_cross_sum)
        {
            max_left=tem_left_low;
            max_right=tem_left_high;
            max_vlaue=tem_left_sum;
        }
        else if (tem_right_sum>=tem_left_sum&&tem_right_sum>=tem_cross_sum)
        {
            max_left=tem_right_low;
            max_right=tem_right_high;
            max_vlaue=tem_right_sum;
        }
        else
        {
            max_left=tem_cross_low;
            max_right=tem_cross_high;
            max_vlaue=tem_cross_sum;
        }
    }
    return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int max_left=0;
    int max_right=0;
    int max_value=0;
    int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    Find_Max_subArray(a,0,15,max_left,max_right,max_value);
    cout<<max_left<<" "<<max_right<<" "<<max_value<<endl;
    system("pause");
    return 0;
}

View Code

递归式： T(n)=2*T(n/2)+Theta(n);n>1

T(n)=theta(1);

非递归线性算法：(4.1-5)

此方是看了我转载的那个伙伴的才有思路,和为负数，就跳过。

 1 // Max_Value.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 
 8 int Max(int *a,int low,int high,int &sub_left,int &sub_right,int &sub_sum)
 9 {
10     if (low==high)
11     {
12         if (a[low]>0)
13         {
14             sub_sum=a[low];
15             sub_left=low;
16             sub_right=high;
17         }
18         else sub_sum=0;
19     }
20     int tempSum=0;
21     for (int i=low;i<=high;i++)
22     {
23         tempSum+=a[i];
24         if (tempSum<=0)
25         {
26             tempSum=0;
27             sub_left=i+1;
28         }
29         if (tempSum>sub_sum)
30         {
31             sub_sum=tempSum;
32             sub_right=i;
33         }
34     }
35     return 0;
36 }
37 int _tmain(int argc, _TCHAR* argv[])
38 {
39     int sub_left=0;
40     int sub_right=0;
41     int sub_sum=0;
42     int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
43     Max(a,0,15,sub_left,sub_right,sub_sum);
44     cout<<sub_left<<" "<<sub_right<<" "<<sub_sum<<endl;
45     system("pause");
46     return 0;
47 }

View Code

只扫描了一遍，时间复杂度为O(n);

以上方法输出结果都一样：7 10 43