最大子序列和：一道题窥探分治与动态规划

 1 #include <iostream>
 2 #include <limits>
 3 
 4 using namespace std;
 5 
 6 struct Tag
 7 {
 8     Tag(int _lowmark, int _highmark, int _sum)
 9     {
10         lowmark = _lowmark;
11         highmark = _highmark;
12         sum = _sum;
13     }
14     int lowmark;
15     int highmark;
16     int sum;
17 };
18 
19 Tag find_maximum_cross_subarr(int a[], int p, int q, int r)
20 {
21     int lowmark;
22     int lowmax = numeric_limits<int>::min();
23     int sum = 0;
24     for (int i = q - 1; i >= p; i--)
25     {
26         sum += a[i];
27         if (sum > lowmax)
28         {
29             lowmark = i;
30             lowmax = sum;
31         }
32     }
33 
34     int highmark;
35     int highmax = numeric_limits<int>::min();
36     sum = 0;
37     for (int i = q; i < r; i++)
38     {
39         sum += a[i];
40         if (sum > highmax)
41         {
42             highmark = i;
43             highmax = sum;
44         }
45     }
46     return Tag(lowmark, highmark + 1, lowmax + highmax);
47 }
48 
49 Tag find_maximum_subarr(int a[], int p, int r)
50 {
51     if (r - p == 1)
52         return Tag(p, r, a[p]);
53 
54     int q = (p + r) / 2;
55     Tag tagleft = find_maximum_subarr(a, p, q);
56     Tag tagright = find_maximum_subarr(a, q, r);
57     Tag tagcross = find_maximum_cross_subarr(a, p, q, r);
58 
59     if (tagleft.sum > tagright.sum && tagleft.sum > tagcross.sum)
60         return tagleft;
61     else if (tagright.sum > tagleft.sum && tagright.sum > tagcross.sum)
62         return tagright;
63     else
64         return tagcross;
65 }
66 
67 int main(int argc, char** argv)
68 {
69     int a[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
70 
71     Tag t = find_maximum_subarr(a, 0, 16);
72 
73     cout << t.sum << t.lowmark << t.highmark << endl;
74 
75     return 0;
76 }

 1 #include <iostream>
 2 #include <limits>
 3 
 4 using namespace std;
 5 
 6 struct Tag
 7 {
 8     Tag(int _l, int _r, int _sum)
 9     {
10         l = _l;
11         r = _r;
12         sum = _sum;
13     }
14     int l;
15     int r;
16     int sum;
17 };
18 
19 Tag find_maximum_subarr(int a[], int n)
20 {
21     int maxsum = numeric_limits<int>::min();
22     int maxlindex = 0;
23     int maxrindex = 0;
24     
25     int sum = 0;
26     int lindex = 0;
27 
28     for (int i = 0; i < n; i++)
29     {
30         if (sum < 0)
31         {
32             sum = a[i];
33             lindex = i;
34         }
35         else
36         {
37             sum += a[i];
38         }
39         if (sum > maxsum)
40         {
41             maxlindex = lindex;
42             maxrindex = i + 1;
43             maxsum = sum;
44         }
45     }
46     return Tag(maxlindex, maxrindex, maxsum);
47 }
48 
49 int main(int argc, char** argv)
50 {
51     int a[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
52 
53     Tag t = find_maximum_subarr(a, 16);
54 
55     cout << t.sum << "," << t.l << "," << t.r << endl;
56     
57 
58     return 0;
59 }