首页 > 代码库 > 【C++】最大子列和

【C++】最大子列和

2024-08-26 21:28:09   219人阅读

　　此题来自《数据结构与算法》，书中一共介绍了四种方法，这里贴出两种。

1.分治递归，对本题来说，虽然有更好的算法，但是用此题理解分治算法感觉挺有用

 1 #include <iostream>
 2 int maxsublink(int *a,int right,int left);
 3 using std::cout;
 4 using std::cin;
 5 
 6 int main()
 7 {
 8     int a[8]={4,-3,5,-2,-1,2,6,-2};
 9     int maxnum=maxsublink(a,0,7);
10     cout<<maxnum;
11     return 0;
12 }
13 int maxsublink(int *a,int left,int right)
14 {
15     int rightmax,leftmax;
16     int leftbordermax,rightbordermax;
17     int leftborder,rightborder;
18 
19     if(left==right)
20       {
21           if(a[left]>0)
22             return a[left];
23         else
24             return 0;
25       }
26     int mid,i;
27     mid=(right+left)/2;
28     leftmax=maxsublink(a,left,mid);
29     rightmax=maxsublink(a,mid+1,right);
30     leftborder=leftbordermax=0;
31     for(i=mid;i>=left;i--)
32     {
33         leftborder+=a[i];
34         if(leftborder>leftbordermax)
35             leftbordermax=leftborder;
36     }
37     rightborder=rightbordermax=0;
38     for(i=mid+1;i<=right;i++)
39     {
40         rightborder+=a[i];
41         if(rightborder>rightbordermax)
42             rightbordermax=rightborder;
43     }
44     int intermax=leftbordermax+rightbordermax;
45     if(intermax>=rightmax)
46     {
47         if(intermax>=leftmax)
48             return intermax;
49         else
50             return leftmax;
51     }
52     else
53     {
54         if(rightmax>=leftmax)
55             return rightmax;
56         else
57             return leftmax;
58     }
59 }

2.遍历整个数组，每个遍历的值保存入thissum，当thissum<0时，thissum置零；当thissum>max时，更新max

　这种方法时间复杂度可以达到O(n)，感觉这种编程方法很值得学习，而且在别的算法中也经常用到，很典型。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 int maxsublink(int *a,int num);
 5 int main()
 6 {
 7     int a[8]={4,-3,5,-2,-1,2,6,-2};
 8     int maxnum=maxsublink(a,8);
 9     cout<<maxnum;
10     return 0;
11 }
12 int maxsublink(int *a,int num)
13 {
14     int i,thissum,maxsum;
15     maxsum=thissum=0;
16     for(i=0;i<num;i++)
17     {
18         thissum+=a[i];
19         if(thissum>maxsum)
20             maxsum=thissum;
21         else if(thissum<0)
22             thissum=0;
23     }
24     return maxsum;
25 }

 

【C++】最大子列和


联系
我们