为一体连串的下标区间,最大子段和难题(马克西姆um

二分查找

   二分查找是基于有序种类的寻找方法(以下要是严峻单调自增),该算法一开首令
[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 的要素的任务 安德拉 ,那样成分 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] 。

 

 

一.主题材料陈述

给定长度为n的大背头连串,a[1…n],
求[1,n]某些子区间[i ,
j]使得a[i]+…+a[j]和最大.只怕求出最大的那几个和.举个例子(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

二分法拓展

  何以统计 √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] 范围内的根。

 

二维最大子段和难题

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

快速幂

  来看二个标题:给定多少个正整数
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 }

 

  

 

3.动态规划法

动态规划的基本原理这里不再赘述,首要探究这些主题素材的建立模型进程和子难点结构.时刻记住三个前提,这里是接连的间隔

  • 令b[j]代表以任务 j 为终端的全数子区间五月最大的八个
  • style=”color: #00八千;”>子难题:如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段和难点.

  装水难题:

  在三个侧边看去是半圆的储水装置,该半圆的半径为
奥迪Q7 ,供给往里面装入低度为 h 的水,使其从左边看去的面积
S1 与半圆面积 S2 的比重恰好为 r 。现给定 RAV4 和 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
,供给算法中不关乎坐标的总结。

 

 

最大子段和主题材料(马克西姆um
Interval Sum)
美丽的动态规划难题,大概全部的算法教材都会波及.本文将剖析最大子段和主题材料的两种不一致频率的解法,以及最大子段和难题的扩大和平运动用.

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).

动态规划法

动态规划法其实正是把二维最大子段和转化为一维最大子段和难题.
转载方法:

  • 咱俩把这一个矩阵划分成n个“条”,条的长短为1到m,通过多少个for遍历所有长度的条
  • 图片 1
  • 下一场,若干个接二连三的条,正是几个子矩阵了,那样难点就随便地转载为一维最大子段和主题材料了
  • 经过求全部这种条,起源为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;

 

难题浅析

子矩阵的概念这里不再赘言,不打听的能够去复习一下线性代数.如下图所示的
图片 2

首先明显一件事情,可以经过精通对角线上的五个因平昔规定三个子矩阵,在二维最大子段和主题素材中,大家渴求的是那般多少个子矩阵,如图中红框所示,个中0<= i <= j <=n-1 , 0 <= p <= q <=
n-1。由此轻松获得多少个O(n^4)的枚举算法.

二. 难题浅析

相关文章