《子数组最大和》

 1 #include<iostream>
 2 using namespace std;
 3 #define N 10000
 4 
 5 int max(int a, int b)
 6 {
 7     int y;
 8     if (a > b&&b < 0)
 9     {
10         y = a;
11     }
12     if (a < b&&a < 0)
13     {
14         y = b;
15     }
16     if (a + b >= a&&a + b >= b)
17     {
18         y = a + b;
19     }
20     return y;
21 }
22 
23 int select(int a[], int l, int r)
24 {
25     int m = (r + l) / 2;
26     if (r == l)
27     {
28         return a[l];
29     }
30     int maxr = a[m+1], maxl = a[m];
31     int ml = a[m], mr = a[m + 1];
32     for (int i = m - 1; i >= l; i--)
33     {
34         ml = ml + a[i];
35         if (maxl <= ml)
36         {
37             maxl = ml;
38         }
39     }
40     for (int i = m + 2; i <= r; i++)
41     {
42         mr = mr + a[i];
43         if (maxr <= mr)
44         {
45             maxr = mr;
46         }
47     }
48     select(a, l, m);
49     select(a, m + 1, r);
50     int u=max(maxr, maxl);
51     return u;
52 }
53 int main()
54 {
55     int n, m, s , a[N];
56     cout << "请输入数组中有几个数字:";
57     cin >> s;
58     cout << "请输入数组中整数的范围(第一个数小于第二个数)：";
59     cin >> n >> m;
60     for (int i = 0; i < s; i++)
61     {
62         a[i] = rand() % (m - n + 1) + n;
63         cout << a[i] << "   ";
64     }
65     cout << endl;
66     int p=select(a, 0, s-1);
67     cout << "子数组的最大和为" << p << endl;
68     return 0;
69 }