ca88亚洲城网站 的高中级地方 mid=(left+right)/2, 为一体连串的下标区间

二分查找

   二分查找是基于有序系列的搜索方法(以下虽然严谨单调自增),该算法一先导令
[left,right] 为一体系列的下标区间,然后每便测试当前 [left,right] 的高中级地点 mid=(left+right)/2
,判断 A[mid]与欲询问的要素 x  的尺寸:

    • 如果
      A[mid]  == x ,表达查找成功,退出查询
    • 如果
      A[mid]  > x ,表明元素 x 在 mid 地方的左侧,由此往左子区间
      [left,mid-1] 继续搜寻
    • 如果
      A[mid]  < x ,表达元素 x 在 mid 地点的右手,因而往右子区间
      [mid+1,right] 继续搜寻

   由此其时间复杂度是
O(logn)。

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 // A[] 为严格递增序列, left 为二分下界, right 为二分上界, x 为欲查询数 
 8 int binarySearch(int A[], int left, int right, int x) {
 9     int mid;        // 中点
10     while(left <= right) {
11         mid = (left+right)/2;
12         if(A[mid] == x)    return mid;
13         else if(A[mid] > x) {
14             right = mid-1;        // 往左区间查询 
15         } else {
16             left = mid+1;        // 往右区间查询 
17         } 
18     } 
19     
20     return -1;                    // 未查询到 
21 } 
22 
23 int main() {
24     const int n = 10;
25     int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};
26     // 查询 3 和 5 
27     printf("%d %d\n", binarySearch(A, 0, n-1, 6), binarySearch(A, 0, n-1, 5)); 
28 
29     return 0;
30 }

 

   那么,假若连串是递减的,只需把上边代码中的  A[mid] > x  改为  A[mid] < x  即可。

  需要留意的是,尽管二分上界超越int 型数据范围的一半,那么语句  mid =
(left+right)/2 
有可能引致溢出,应改为  mid = left +
(right-left)/2 。

 

  

  接下去探讨更进一步的题材:假诺递增连串A 中的元素可能再一次,那么咋样对给定的欲询问元素 x
,求出体系中首先个高于等于 x 的因素的职务 L 以及第一个超越x 的要素的职位 R ,这样元素 x 在体系中的存在区间就是 [L,R) 。

  先来设想第一个小问:求系列中的首个高于等于
x 的因素的岗位。

    •  如果
      A[mid] ≥ x ,表达第一个超越等于 x 的因素的职位一定在 mid 处或
      mid 的左手,应往左子区间 [left,mid] 继续查询,即令 right = mid

    •  如果
      A[mid] < x ,表达第一个超过等于 x 的因素的岗位一定在
      mid 的左侧,应往右子区间 [mid+1,right] 继续查询,即令 left =
      mid+1 。

       1 // A[] 为递增序列,x 为欲查询的数,函数返回第一个大于等于 x 的元素的位置
       2 // left,right 为左右边界 
       3 int lower_bound(int A[], int left, int right, int x) {
       4     int mid;        // 中点
       5     while(left < right) {
       6         mid = (left+right)/2;
       7         if(mid >= x) {        // 中间的数大于等于 x 
       8             right = mid;    // 左区间 
       9         } else {            // 中间的数小于 x 
      10             left = mid+1;    // 右区间 
      11         }
      12     } 
      13     
      14     return left; 
      15 }
      
    •  考虑到欲询问元素有可能比连串中的所有因素都要大,此时应当再次来到n ,因而二分上界是 n ,故二分的发端区间为 [left,right] =
      [0,n] 。

  

  接下去解决第二小问:求系列中第一个高于
x 的因素的岗位。

    • 如果
      A[mid] > x ,表明首个超越 x 的元素的地方一定在 mid 处或
      mid 的右侧,应往左子区间 [left,mid] 继续查询,即令 right = mid

    • 如果
      A[mid] ≤ x ,表达第一个高于 x 的元素的岗位一定在
      mid 的入手,应往右子区间 [mid+1,right] 继续查询,即令 left =
      mid+1 。

       1 // A[] 为递增序列,x 为欲查询的数,函数返回第一个大于 x 的元素的位置
       2 // left,right 为左右边界,传入的初值为 [0,n] 
       3 int upper_bound(int A[], int left, int right, int x) {
       4     int mid;        // 中点
       5     while(left < right) {
       6         mid = (left+right)/2;
       7         if(mid > x) {        // 中间的数大于 x 
       8             right = mid;    // 左区间 
       9         } else {            // 中间的数小于等于 x 
      10             left = mid+1;    // 右区间 
      11         }
      12     } 
      13     
      14     return left; 
      15 } 
      

       

 

  读者会发觉,
lower_bound 函数 和  upper_bound 函数的代码低度相似,其实这七个函数都在缓解这样一个题材:摸索有序体系中第一个满意某条件的元素的职务。此处统计了化解此类问题的固化模版:

 1 // 解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模版
 2 // 二分区间为左闭右闭的 [left,right],初值必须能覆盖解的所有可能取值 
 3 int upper_bound(int A[], int left, int right, int x) {
 4     int mid;        // 中点
 5     while(left < right) {
 6         mid = (left+right)/2;
 7         if( 条件成立 ) {        // 条件成立,第一个满足条件的元素位置 <= mid 
 8             right = mid;    // 左区间 
 9         } else {            // 条件不成立,第一个满足条件的元素位置 > mid 
10             left = mid+1;    // 右区间 
11         }
12     } 
13     
14     return left;          // 返回夹出来的位置   
15 } 

 

 

   此外,如果想要寻找最有一个满足“条件 C”的元素的地点,则可以先求第一个满意 “条件
!C”的元素的职位,然后将该地方减 1 即可

  
而当二分区间是左开右闭区间 (left,right] 时,循环条件应当是  left+1 <
right ,这样当退出循环时有  left+1 == right  创立,使得
(left,right] 才是绝无仅有地点。且二分区间开始值应为 (-1,n] 。

 

 

二分查找

   二分查找是按照有序连串的追寻方法(以下即便严酷单调自增),该算法一先河令
[left,right] 为一切连串的下标区间,然后每便测试当前 [left,right] 的中间地点 mid=(left+right)/2
,判断 A[mid]与欲询问的因素 x  的大大小小:

    • 如果
      A[mid]  == x ,表达查找成功,退出查询
    • 如果
      A[mid]  > x ,表明元素 x 在 mid 地点的左侧,由此往左子区间
      [left,mid-1] 继续搜寻
    • 如果
      A[mid]  < x ,表达元素 x 在 mid 地方的左侧,由此往右子区间
      [mid+1,right] 继续搜寻

   因而其时间复杂度是
O(logn)。

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 // A[] 为严格递增序列, left 为二分下界, right 为二分上界, x 为欲查询数 
 8 int binarySearch(int A[], int left, int right, int x) {
 9     int mid;        // 中点
10     while(left <= right) {
11         mid = (left+right)/2;
12         if(A[mid] == x)    return mid;
13         else if(A[mid] > x) {
14             right = mid-1;        // 往左区间查询 
15         } else {
16             left = mid+1;        // 往右区间查询 
17         } 
18     } 
19     
20     return -1;                    // 未查询到 
21 } 
22 
23 int main() {
24     const int n = 10;
25     int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};
26     // 查询 3 和 5 
27     printf("%d %d\n", binarySearch(A, 0, n-1, 6), binarySearch(A, 0, n-1, 5)); 
28 
29     return 0;
30 }

 

   那么,如若系列是递减的,只需把下面代码中的  A[mid] > x  改为  A[mid] < x  即可。

  需要专注的是,如果二分上界超过int 型数据范围的一半,那么语句  mid =
(left+right)/2 
有可能造成溢出,应改为  mid = left +
(right-left)/2 。

 

  

  接下去商量更进一步的题目:假如递增系列A 中的元素可能再度,那么如何对给定的欲询问元素 x
,求出连串中率先个超越等于 x 的元素的职务 L 以及第一个高于
x 的因素的职位 R ,这样元素 x 在连串中的存在区间就是 [L,R) 。

  先来考虑第一个小问:求系列中的第一个超越等于
x 的元素的地点。

    •  如果
      A[mid] ≥ x ,表达第一个高于等于 x 的元素的职位一定在 mid 处或
      mid 的右侧,应往左子区间 [left,mid] 继续查询,即令 right = mid

    •  如果
      A[mid] < x ,表达首个高于等于 x 的要素的地点一定在
      mid 的动手,应往右子区间 [mid+1,right] 继续查询,即令 left =
      mid+1 。

       1 // A[] 为递增序列,x 为欲查询的数,函数返回第一个大于等于 x 的元素的位置
       2 // left,right 为左右边界 
       3 int lower_bound(int A[], int left, int right, int x) {
       4     int mid;        // 中点
       5     while(left < right) {
       6         mid = (left+right)/2;
       7         if(mid >= x) {        // 中间的数大于等于 x 
       8             right = mid;    // 左区间 
       9         } else {            // 中间的数小于 x 
      10             left = mid+1;    // 右区间 
      11         }
      12     } 
      13     
      14     return left; 
      15 }
      
    •  考虑到欲询问元素有可能比类别中的所有因素都要大,此时应该再次来到n ,由此二分上界是 n ,故二分的初叶区间为 [left,right] =
      [0,n] 。

  

  接下去解决第二小问:求体系中首先个高于
x 的要素的地方。

    • 如果
      A[mid] > x ,表明第一个超过 x 的要素的职位一定在 mid 处或
      mid 的左边,应往左子区间 [left,mid] 继续查询,即令 right = mid

    • 如果
      A[mid] ≤ x ,表明第一个高于 x 的因素的地点一定在
      mid 的出手,应往右子区间 [mid+1,right] 继续查询,即令 left =
      mid+1 。

       1 // A[] 为递增序列,x 为欲查询的数,函数返回第一个大于 x 的元素的位置
       2 // left,right 为左右边界,传入的初值为 [0,n] 
       3 int upper_bound(int A[], int left, int right, int x) {
       4     int mid;        // 中点
       5     while(left < right) {
       6         mid = (left+right)/2;
       7         if(mid > x) {        // 中间的数大于 x 
       8             right = mid;    // 左区间 
       9         } else {            // 中间的数小于等于 x 
      10             left = mid+1;    // 右区间 
      11         }
      12     } 
      13     
      14     return left; 
      15 } 
      

       

 

  读者会发现,
lower_bound 函数 和  upper_bound 函数的代码低度相似,其实这六个函数都在化解这样一个问题:查找有序体系中率先个满足某条件的要素的职务。此处总计了然决此类问题的固定模版:

 1 // 解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模版
 2 // 二分区间为左闭右闭的 [left,right],初值必须能覆盖解的所有可能取值 
 3 int upper_bound(int A[], int left, int right, int x) {
 4     int mid;        // 中点
 5     while(left < right) {
 6         mid = (left+right)/2;
 7         if( 条件成立 ) {        // 条件成立,第一个满足条件的元素位置 <= mid 
 8             right = mid;    // 左区间 
 9         } else {            // 条件不成立,第一个满足条件的元素位置 > mid 
10             left = mid+1;    // 右区间 
11         }
12     } 
13     
14     return left;          // 返回夹出来的位置   
15 } 

 

 

   其它,如若想要寻找最有一个满意“条件 C”的要素的岗位,则可以先求第一个满意 “条件
!C”的元素的地点,然后将该岗位减 1 即可

  
而当二分区间是左开右闭区间 (left,right] 时,循环条件应当是  left+1 <
right ,这样当退出循环时有  left+1 == right  创制,使得
(left,right] 才是唯一地方。且二分区间起先值应为 (-1,n] 。

 

 

最大子段和问题(马克斯(Max)imum
Interval Sum)
经典的动态规划问题,几乎所有的算法教材都会涉嫌.本文将分析最大子段和题材的三种不同频率的解法,以及最大子段和题材的扩大和运用.

二分法拓展

  什么样总括 √2 的近似值

  对
f(x) = x2 来说,令浮点型 left 和 right 的初值分别为 1 和
2,然后依据 left 和 right 的当心 mid 处 f(x) 的值与
2 的高低来挑选子区间展开逼近:

    •  如果
      f(mid) > 2,说明 mid > √2,应当在
      [left,mid]的限量内连续逼近,故令 right = mid 。
    •  如果
      f(mid) < 2,说明 mid < √2,应当在
      [mid,right]的范围内连续逼近,故令 left= mid 。

  上边六个步骤当
right – left < 10-5 时结束。

 1 const double eps = 1e-5;    // 精度为 10^-5
 2 double f(double x) {        // 计算 f(x) 
 3     return x * x - 2;
 4 } 
 5 
 6 double calSqrt() {
 7     double left=1, right=2, mid;    // [left,right] = [1,2] 
 8     while(right - left > eps) {
 9         mid = (left+right)/2;
10         if(f(mid) > 0) {            // mid > sqrt(2) 
11             right = mid;            // 左区间 
12         } else {                    // mid < sqrt(2) 
13             left = mid;                // 右区间
14         }
15     }
16     
17     return mid;                        // 返回 mid 作为近似值 
18 }

 

 

 

  事实上,总括 √2 的近似值的题材其实是如此一个题目标特例:给定一个定义在
[L,R] 上的干瘪函数 f(x) ,求方程 f(x) = 0 的根

  此时只需修改上述代码
f 函数有的即可,分明总括 √2 的近似值等价于求 f(x) = x2 – 2 =
0 在 [1,2] 范围内的根。

 

二分法拓展

  什么总括 √2 的近似值

  对
f(x) = x2 来说,令浮点型 left 和 right 的初值分别为 1 和
2,然后依据 left 和 right 的中部 mid 处 f(x) 的值与
2 的分寸来采纳子区间开展逼近:

    •  如果
      f(mid) > 2,说明 mid > √2,应当在
      [left,mid]的范围内继续逼近,故令 right = mid 。
    •  如果
      f(mid) < 2,说明 mid < √2,应当在
      [mid,right]的限制内继续逼近,故令 left= mid 。

  上边七个步骤当
right – left < 10-5 时结束。

 1 const double eps = 1e-5;    // 精度为 10^-5
 2 double f(double x) {        // 计算 f(x) 
 3     return x * x - 2;
 4 } 
 5 
 6 double calSqrt() {
 7     double left=1, right=2, mid;    // [left,right] = [1,2] 
 8     while(right - left > eps) {
 9         mid = (left+right)/2;
10         if(f(mid) > 0) {            // mid > sqrt(2) 
11             right = mid;            // 左区间 
12         } else {                    // mid < sqrt(2) 
13             left = mid;                // 右区间
14         }
15     }
16     
17     return mid;                        // 返回 mid 作为近似值 
18 }

 

 

 

  事实上,总括 √2 的近似值的题目实际上是这么一个问题的特例:给定一个定义在
[L,R] 上的平淡函数 f(x) ,求方程 f(x) = 0 的根

  此时只需修改上述代码
f 函数片段即可,显然总括 √2 的近似值等价于求 f(x) = x2 – 2 =
0 在 [1,2] 范围内的根。

 

一.题目讲述

给定长度为n的平头体系,a[1…n],
求[1,n]某个子区间[i ,
j]使得a[i]+…+a[j]和最大.或者求出最大的那多少个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

  装水问题:

  在一个侧面看去是半圆的储水装置,该半圆的半径为
R ,要求往里面装入低度为 h 的水,使其从侧面看去的面积
S1 与半圆面积 S2 的比重恰好为 r 。现给定 R 和 r
,求低度 h 。

  在这多少个题目中,需要寻找水面高度h 与 面积比例 r 之间的关联。而很明朗,随着水面提高,面积比重
r 一定是增大的。由此可以博得这么的笔触:在 [0,R] 范围内对水面中度h 举办二分,总括在低度下边积比例 r 的值。

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const double PI = acos(-1.0);     // PI
 8 const double eps = 1e-5;        // 精度为 10^-5
 9 
10 double f(double R, double h) {    // 计算 r = f(h) 
11     double alpha = 2 * acos((R-h)/R);
12     double L = 2 * sqrt(R*R - (R-h)*(R-h));
13     double S1 = alpha * R * R / 2 - L *(R-h) / 2;
14     double S2 = PI * R * R /2;
15     return S1 / S2; 
16 } 
17 
18 double solve(double R, double r) {
19     double left = 0, right = R, mid; 
20     while(right-left > eps) {
21         mid = (left+right)/2;
22         if(f(R, mid) > r) {    
23             right = mid;        // 左区间 [left,mid] 
24         } else {
25             left = mid;            // 右区间 [mid,right] 
26         }
27     }
28     
29     return mid;                    // 返回 mid 即为所求 h  
30 }
31 
32 int main() {
33     double R, r;
34     scanf("%lf%lf", &R, &r);
35     printf("%.4f\n", solve(R, r)); 
36 
37     return 0;
38 }

 

 

  木棒切割问题:

  给定
N 根木棒,长度均已知,现在愿意经过切割它们来获取至少
K 段长度相等的木棍(长度必须为整数),问这多少个长度相等的木棒最长能有多少长度。

  首先可以小心到一个定论:假设长度相等的木棒的长度
L 越长,那么得到的木棍段数越少。从这些角度出发便足以先到本题的算法,即二分答案,依照对当下长度
L 来说能收获的木棒段数 k 与 K 的分寸关系展开二分。

 

  终极一个题材(没有思路):

  给定
N 个线段的长短,试将它们头尾相接(顺序任意)地组合成一个凸多边形,使得凸多边形的外接圆的半径最大,求该最大半径。其中
N 不超越 105 ,线段长度均不超越 100
,要求算法中不关乎坐标的盘算。

 

 

  装水问题:

  在一个侧面看去是半圆的储水装置,该半圆的半径为
R ,要求往里面装入低度为 h 的水,使其从侧面看去的面积
S1 与半圆面积 S2 的比例恰好为 r 。现给定 R 和 r
,求中度 h 。

  在这一个题材中,需要摸索水面高度h 与 面积比例 r 之间的关系。而很明朗,随着水面进步,面积比例
r 一定是外加的。因此可以取得那样的思绪:在 [0,R] 范围内对水面低度h 举行二分,统计在低度下边积比重 r 的值。

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const double PI = acos(-1.0);     // PI
 8 const double eps = 1e-5;        // 精度为 10^-5
 9 
10 double f(double R, double h) {    // 计算 r = f(h) 
11     double alpha = 2 * acos((R-h)/R);
12     double L = 2 * sqrt(R*R - (R-h)*(R-h));
13     double S1 = alpha * R * R / 2 - L *(R-h) / 2;
14     double S2 = PI * R * R /2;
15     return S1 / S2; 
16 } 
17 
18 double solve(double R, double r) {
19     double left = 0, right = R, mid; 
20     while(right-left > eps) {
21         mid = (left+right)/2;
22         if(f(R, mid) > r) {    
23             right = mid;        // 左区间 [left,mid] 
24         } else {
25             left = mid;            // 右区间 [mid,right] 
26         }
27     }
28     
29     return mid;                    // 返回 mid 即为所求 h  
30 }
31 
32 int main() {
33     double R, r;
34     scanf("%lf%lf", &R, &r);
35     printf("%.4f\n", solve(R, r)); 
36 
37     return 0;
38 }

 

 

  木棒切割问题:

  给定
N 根木棒,长度均已知,现在梦想通过切割它们来得到至少
K 段长度相等的木棒(长度必须为整数),问这一个长度相等的木棍最长能有多少长度。

  首先可以小心到一个结论:假若长度相等的木棍的长短
L 越长,那么拿到的木棒段数越少。从这些角度出发便得以先到本题的算法,即二分答案,依据对当下长度
L 来说能获取的木棍段数 k 与 K 的轻重缓急关系进展二分。

 

  最终一个题目(没有思路):

  给定
N 个线段的长短,试将它们头尾相接(顺序任意)地组合成一个凸多边形,使得凸多边形的外接圆的半径最大,求该最大半径。其中
N 不超过 105 ,线段长度均不超过 100
,要求算法中不涉及坐标的统计。

 

 

二. 问题分析

快速幂

  来看一个题材:给定四个正整数
a、b、m(a<109, b<1018,
1<m<109),求 ab % m 。

  显著无法间接总结,这里要利用高效幂的做法,它按照二分的想想。疾速幂基于以下事实:

    • 如果
      b 是奇数,那么有 ab = a * ab-1
    • 如果
      b 是偶数,那么有 ab = ab/2 *
      ab/2 。

  快速幂的递归写法如下:

1 LL binaryPow(LL a, LL b, LL m) {
2     if(b == 0)    return 1;
3     // b 为奇数
4     if(b % 2) return a * binaryPow(a, b-1, m) % m;
5     else {    // b 为偶数 
6         LL mu1 = binaryPow(a, b/2, m);
7         return mu1 * mu1 % m;
8     }
9 } 

  

  接下去探究一下快速幂的迭代写法。

  对 ab 来说,假若把 b 写成二进制,那么
b 就足以写成几何二次幂之和。例如 13 的二进制是 1101 ,那么
13=23+22+20,所以 a13 = a8 * a4 * a1

  我们得以把 ab  表示成 a2k、… 、a8、 a4、a2、a1 中多少项的乘积,其中倘诺b 的二进制的 i 号位为1,那么项 a2i 就被选中。

  连忙幂的迭代写法:

 1 LL binaryPow(LL a, LL b, LL m) {
 2     LL ans = 1;
 3     while(b > 0) {
 4         if(b & 1) {        // 末位为 1 
 5             ans = ans * a % m;        // 令 ans 累乘上 a  
 6         }
 7         a = a * a % m;    // 令 a 平方
 8         b >>= 1;        // b 右移1,相当于除2 
 9     }
10     return ans; 
11 }

 

  

 

快速幂

  来看一个问题:给定五个正整数
a、b、m(a<109, b<1018,
1<m<109),求 ab % m 。

  显著无法直接总括,这里要运用高效幂的做法,它依据二分的想想。急忙幂基于以下事实:

    • 如果
      b 是奇数,那么有 ab = a * ab-1
    • 如果
      b 是偶数,那么有 ab = ab/2 *
      ab/2 。

  快捷幂的递归写法如下:

1 LL binaryPow(LL a, LL b, LL m) {
2     if(b == 0)    return 1;
3     // b 为奇数
4     if(b % 2) return a * binaryPow(a, b-1, m) % m;
5     else {    // b 为偶数 
6         LL mu1 = binaryPow(a, b/2, m);
7         return mu1 * mu1 % m;
8     }
9 } 

  

  接下去研究一下赶快幂的迭代写法。

  对 ab 来说,虽然把 b 写成二进制,那么
b 就足以写成几何二次幂之和。例如 13 的二进制是 1101 ,那么
13=23+22+20,所以 a13 = a8 * a4 * a1

  我们能够把 ab  表示成 a2k、… 、a8、 a4、a2、a1 中若干项的乘积,其中假设b 的二进制的 i 号位为1,那么项 a2i 就被入选。

  飞速幂的迭代写法:

 1 LL binaryPow(LL a, LL b, LL m) {
 2     LL ans = 1;
 3     while(b > 0) {
 4         if(b & 1) {        // 末位为 1 
 5             ans = ans * a % m;        // 令 ans 累乘上 a  
 6         }
 7         a = a * a % m;    // 令 a 平方
 8         b >>= 1;        // b 右移1,相当于除2 
 9     }
10     return ans; 
11 }

 

  

 

1.穷举法

穷举应当是每个人都要学会的一种方法,这里其实是要穷举所有的[1,n]里头的距离,所以大家用两重循环,可以很自由地成功遍历所有子区间,一个意味开始地点,一个意味终点地方.代码如下:

?

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
int start = 0;//起始位置
int end = 0;  //结束位置
int max = 0;
for(int i = 1; i <= n; ++i)
{
    for(int j = i; j <= n;++j)
    {
        int sum = 0;
        for(int k = i; k <=j; ++k)
            sum += a[k];
        if(sum > max)
        {
           start = i;
           end = j;
           max = sum;
        }
    }
}

以此算法是几乎所有人都能体悟的,它所急需的精打细算时间是O(n^3).当然,这么些代码还足以做点优化,实际上我们并不需要每一次都重复从起初地点求和加到终点地点.可以充分利用在此之前的盘算结果.

要么我们换一种穷举思路,对于起源i,我们遍历所有长度为1,2,…,n-i+1的子区间和,以求得和最大的一个.这样也遍历了装有的起源的不比尺寸的子区间,同时,对于同样起点的不等长短的子区间,可以行使前面的乘除结果来计量前边的.

例如,i为起源长度为2的子区间和就相当于长度为1的子区间的和+a[i+1]即可,这样就省掉了一个巡回,总计时间复杂度裁减到了O(n^2).代码如下:

?

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
int start = 0;//起始位置
int end = 0;//结束位置
int max = 0;
for(int i = 1; i <= n; ++i)
{
    int sum = 0;
    for(int j = i; j <= n;++j)
    {
        sum += a[j];
        if(sum > max)
        {
           start = i;
           end = j;
           max = sum;
        }
    }
}

2.分治法

求子区间及最大和,从结构上是十分适合分治法的,因为所有子区间[start,
end]只可能有以下二种可能:

  • 在[1, n/2]这多少个区域内
  • 在[n/2+1, n]其一区域内
  • 起源位于[1,n/2],终点位于[n/2+1,n]内

如上两种情形的最大者,即为所求.
前三种情状符合子问题递归特性,所以递归可以求出.
对于第二种状态,则需要单独处理.
第二种情景必然包括了n/2和n/2+1多少个职务,这样就足以选用第两种穷举的思路求出:

  • 以n/2为终端,往左移动扩大,求出和最大的一个left_max
  • 以n/2+1为起源,往右移动扩充,求出和最大的一个right_max
  • left_max+right_max是第三种情景恐怕的最大值

参考代码如下:

?

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
int maxInterval(int *a, int left, int right)
 {
    if(right==left)
      return a[left]>0?a[left]:0;
 
    int center = (left+right)/2;
    //左边区间的最大子段和
    int leftMaxInterval = maxInterval(a,left,center);
    //右边区间的最大子段和
    int rightMaxInterval= maxInterval(a,center+1,right);
 
    //以下求端点分别位于不同部分的最大子段和
 
    //center开始向左移动
    int sum = 0;
    int left_max = 0;
    for(int i = center; i >= left; –i)
    {
       sum += a[i];
       if(sum > left_max)
          left_max = sum;
    }
    //center+1开始向右移动
    sum = 0;
    int right_max = 0;
    for(int i = center+1; i <= right; ++i)
    {
       sum += a[i];
       if(sum > right_max)
         right_max = sum;
    }
    int ret = left_max+right_max;
    if(ret < leftMaxInterval)
        ret = leftMaxInterval;
    if(ret < rightMaxInterval)
        ret = rightMaxInterval;
    return ret;
 }

分治法的难题在于第二种情形的知道,这里应该吸引第二种情形的表征,也就是当中有六个稳定,然后分别往几个趋势扩张,以遍历所有属于第二种情景的子区间,求的最大的一个,如若要求得实际的距离,稍微对上述代码做点修改即可.
分治法的计量时间复杂度为O(nlogn).

3.动态规划法

动态规划的基本原理这里不再赘言,首要研讨这一个题材的建模过程和子问题结构.时刻记住一个前提,这里是接二连三的距离

  • 令b[j]表示以职务 j 为终极的所有子区间中和最大的一个
  • style=”color: #008000;”>子问题:如j为极端的最大子区间包含了职务j-1,则以j-1为终极的最大子区间必然包括在里边
  • 如果b[j-1] >0, 那么强烈b[j] = b[j-1] +
    a[j],用事先最大的一个增长a[j]即可,因为a[j]务必带有
  • 如果b[j-1]<=0,那么b[j] = a[j]
    ,因为既然最大,前边的负数必然无法使您更大

对此这种子问题社团和最优化问题的讲明,可以参见算法导论上的“剪切法”,即只要不包括子问题的最优解,把你一旦的解粘帖上去,会得出子问题的最优化争辩.表达如下

  • 令a[x,y]表示a[x]+…+a[y] , y>=x
  • 假诺以j为极端的最大子区间 [s, j]
    包含了j-1那一个职位,以j-1为终端的最大子区间[ r, j-1]并不含有其中
  • 即假设[r,j-1]不是[s,j]的子区间
  • 存在s使得a[s, j-1]+a[j]为以j为终端的最大子段和,这里的 style=”font-size: large; color: #ff0000;”>r != s 
  • 由于[r, j -1]是最优解,
    所以a[s,j-1]<a[r, j-1],所以a[s,j-1]+a[j]<a[r,
    j-1]+a[j]
  • 与[s,j]为最优解顶牛.

参考代码如下:

?

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
int max = 0;
int b[n+1];
int start = 0;
int end = 0;
memset(b,0,n+1);
for(int i = 1; i <= n; ++i)
 {
   if(b[i-1]>0)
   {
     b[i] = b[i-1]+a[i];
   }else{
     b[i] = a[i];
   }
   if(b[i]>max)
     max = b[i];
 }

动态规划法的推断时间复杂度为O(n),是最优的解,这里推荐磨炼一下UVA507来加深领会.
我原先的题解:

http://www.stackpop.org/blog/html/y2007/371_uva_507.html

 

俺们总括一下二维最大子段和问题,以及最大m段和问题.

二维最大子段和问题

二维最大子段和题材又称之为最大子矩阵问题,给定一个m行n列的整数矩阵A,试求A的一子矩阵,使其各要素之和最大

题材分析

子矩阵的定义这里不再赘言,不了解的可以去复习一下线性代数.如下图所示的
ca88亚洲城网站 1

首先明确一件事情,可以经过了然对角线上的两个要一贯规定一个子矩阵,在二维最大子段和问题中,我们渴求的是这般一个子矩阵,如图中红框所示,其中
0<= i <= j <=n-1 , 0 <= p <= q <=
n-1。由此容易得到一个O(n^4)的枚举算法.

动态规划法

动态规划法其实就是把二维最大子段和转账为一维最大子段和问题.
转车方法:

  • 俺们把这多少个矩阵划分成n个“条”,条的长短为1到m,通过六个for遍历所有长度的条
  • ca88亚洲城网站 2
  • 然后,若干个连续的条,就是一个子矩阵了,这样问题就肆意地转化为一维最大子段和问题了
  • 通过求所有这种条,起点为i,长度为1到m-i+1的“条”的最大子段和,就可以求出整个矩阵的最大子矩阵了
  • 切实枚举长条的时候,同一起源的长短,由于“条”的例外长度间能够接纳以前的结果
  • 比如令b[k][i][j]表示第k个长“条”区间从i到j的和,那么b[k][i][j+1]
    = b[k][i][j]+a[j][k]
  • 本来,实际编程的时候,由于以前的结果求完一维最大子段和后,便不需要保留,所以只需要一维数组b即可

参照代码如下:

?

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
//标准的一维最大子段和
int maxSubInterval(int *data, int n)
{
    int max = 0;
    int b = 0;
    for(int i = 0; i != n; ++i)
    {
       if(b > 0)
       {
           b = b+data[i];
       }else{
           b = data[i];
       }
       if(b>max)
          max = b;
    }
    return max;
}
 
int maxSubMatrix(int (*a)[10], int m, int n)
{
    int max = 0;
    //b[k]记录第k个“条”的和
    int *b = new int[n+1];
    for(int i = 0; i != m; ++i)
    {
        //“条”的和先置为0
        for(int k = 0; k != n; ++k)
            b[k] = 0;
        //起点为i,长度为j-i+1的条
        //相同起点,长度为k的“条”的和,等于长度为k-1的“条”的和加上当前元素a[j][k]
        for(int j = i; j != m; ++j)
        {
            for(int k = 0; k != n; ++k)
                b[k] += a[j][k];
            int sum = maxSubInterval(b,n);
            if(sum > max)
                max = sum;
        }
    }
        free(b);
    return max;

 

相关文章