?1?/**
?2??*分治法求最大子數組
?3??*yaoC?2014-09-06
?4??*Θ(nlg(n))
?5??*/
?6?
?7?#include<iostream>
?8?using?namespace?std;
?9?
10?#define?neg_infinity?-999999
11?
12?//一個子數組的開始下標，結束下標和值的和
13?struct?indices_and_value
14?{
15?????int?left;
16?????int?right;
17?????int?value;
18?};
19?
20?/**
21??*?[findMaxCrossingSubarray?找到跨越中點的最大子數組]
22??*?@param??A?????[輸入數組]
23??*?@param??low???[數組開始下標]
24??*?@param??mid???[數組中間下標]
25??*?@param??heigh?[數組結束下標]
26??*?@return???????[所求子數組的開始結束下標、值的和]
27??*/
28?indices_and_value?findMaxCrossingSubarray(int*?A,?int?low,?int?mid,?int?heigh)
29?{
30?????int?sum?=?0;
31?????int?left_sum?=?neg_infinity;//最大子數組在中點左邊的值的和
32?????indices_and_value?p;
33?????for?(int?i?=?mid;?i?>=?low;?i--)
34?????{
35?????????sum?+=?A[i];
36?????????if?(sum>left_sum)
37?????????{
38?????????????left_sum?=?sum;
39?????????????p.left?=?i;
40?????????}
41?????}
42?????sum?=?0;
43?????int?right_sum?=?neg_infinity;//最大子數組在中點右邊的值的和
44?????for?(int?i?=?mid?+?1;?i?<=?heigh;?i++)
45?????{
46?????????sum?+=?A[i];
47?????????if?(sum>right_sum)
48?????????{
49?????????????right_sum?=?sum;
50?????????????p.right?=?i;
51?????????}
52?????}
53?????p.value?=?left_sum?+?right_sum;
54?????return?p;
55?}
56?
57?/**
58??*?[findMaxSubarray?找到非跨越中點的最大子數組]
59??*?@param??A?????[輸入數組]
60??*?@param??low???[數組開始下標]
61??*?@param??heigh?[數組結束下標]
62??*?@return???????[所求子數組的開始結束下標、值的和]
63??*/
64?indices_and_value?findMaxSubarray(int*?A,?int?low,?int?heigh)
65?{
66?????int?mid?=?(low?+?heigh)?/?2;//數組中點
67?????indices_and_value?p;
68?????if?(low?==?heigh)//base?case:only?one?element
69?????{
70?????????p.left?=?low;
71?????????p.right?=?low;
72?????????p.value?=?A[low];
73?????}
74?????else//recursive?case
75?????{
76?????????indices_and_value?left?=?findMaxSubarray(A,?low,?mid);
77?????????indices_and_value?cross?=?findMaxCrossingSubarray(A,low,mid,heigh);
78?????????indices_and_value?right?=?findMaxSubarray(A,mid?+?1,heigh);
79?????????if?(left.value>cross.value)
80?????????????p?=?left;
81?????????else
82?????????{
83?????????????if?(right.value>cross.value)
84?????????????????p?=?right;
85?????????????else?p?=?cross;
86?????????}
87?????}
88?????return?p;
89?}
90?
91?int?main()
92?{
93?????int?test[]?=?{?0,?13,?-3,?-25,?20,?-3,?-16,?-23,?18,?20,?-7,?12,?-5,?-22,?15,?-4,?7?};
94?????indices_and_value?p;
95?????p?=?findMaxSubarray(test,?0,?16);//(8,11,43)
96?????cout?<<"("<<?p.left?<<?","?<<?p.right?<<?","?<<?p.value?<<")"<<?endl;
97?}

轉載于:https://www.cnblogs.com/yaoC/p/3959515.html

總結

以上是生活随笔為你收集整理的分治法求最大子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。