二种求解最浦这续子数组的算法

遇到一本好书,也去观摩观摩,  本文主要介绍和讨论的问题和介绍的算法(点击跳转),本文主要介绍三大类问题和它们衍生的问题,于是兴致勃勃将系列相关都复习了一遍qwq,求解最大连续子数组的内容在《算法导论》这本书上面是作为分治算法的一个例子来进行讲解的,然后遍历以它们为起点的子数组

图片 5

Java编制程序数组中最大子矩阵简便解法达成代码,java数组

正文商讨的关键是Java编制程序数组中最大子矩阵的连带内容,具体介绍如下。

图片 1

蒙受叁个好人,可以转移平生;碰到一本好书,又何尝不是啊?

多年来在读书
左程云先生的《技术员代码面试指南–IT名企算法与数据结构标题最优解》时就极度的有清醒。提出有那上边爱好的博友,也去观摩观摩。

书中等教育授的依靠栈的数组的最大矩阵的算法很杰出,然而博主技艺轻巧,未能通透到底的精通该算法的精粹,不过依据这么些挂念,博主想出了一种简易的应对此类难点的算法,现概述如下。

核激情想

先来看一张图吧,大家就能够大要的接头了。

图片 2

如图,每三个轮次都以一遍运算,而大家的主题正是本着那每二个轮次的中间的演算。

总括出每一层连接不间断的最大尺寸

也等于说,大家是最那些数组进行由下至上的轮次计算,然后针对每一轮就足以测算出本轮次能够得出的连年最大子矩阵的面积。然后只必要相比每贰个轮次的最大的极其数据,重返就能够求出该数组最大的连接的子矩阵的面积了。

代码

好了,有了下面的宗旨绪想的铺垫,我们就足以入手工编织制代码了。(即便自个儿也认为自个儿并不曾说的很明亮,见谅见谅)。

package stack_and_queue;
/**
 * @author 郭 璞<br>
 *  根据数组来计算连续的最大的矩形区域的面积
 */
public class MaxRectangle {
 public static void main(String[] args) {
  Integer[] arr = { 2, 1, 3, 5, 7, 6, 4 };
  Integer maxRectangle = maxRectangleArea(arr);
  System.out.println("数组中最大的连续的矩形区域的面积为: " + maxRectangle);
 }
 /**
 * @param arr
 * @return 数组中连续矩形区域的最大面积
 */
 private static Integer maxRectangleArea(Integer[] arr) {
  int[] result = new int[arr.length];
  // 对数组进行遍历式的计算,由底向上不间断的连续长度
  for (int i = 1; i <= arr.length; i++) {
   // 当前轮次 中实现对连续长度的累加的临时取值
   int templen = 0;
   // 记录本轮高度下的最大连续长度
   int templen_max = 0;
   // 内层循环应该是从数组首部开始,而从当先层下标开始会导致前面部分数据的丢失
   for (int j = 1; j <= arr.length; j++) {
    if (arr[j - 1] >= i) {
     templen += 1;
     templen_max = templen;
    } else {
     templen = 0;
    }
   }
   result[i - 1] = i * templen_max;
   // System.out.println("第" + i + "层连续不间断的最大长度为:" + templen_max);
  }
  // 求得结果集数组中数值最大的那个数,即为所求连续区域中的最大的矩形域的面积
  int maxArea = 0;
  for (int i = 0; i < result.length; i++) {
   maxArea = maxArea > result[i] ? maxArea : result[i];
  }
  // 将所求得的最大连续矩形域的面积返回
  return maxArea;
 }
}

代码中的注释也相比较的周密,就不再过多的废话了。

测试

下边就对数组进行测量检验。首先以本文起始图片上所示的数组来张开测量试验呢。

Integer[] arr = {2,1,3,5,7,6,4}
···

数组中最大的总是的矩形区域的面积为: 16

然后我们修改一下数组否月素的值,来极度的测验看看结果是还是不是科学。

图片 3

Integer[] arr = {2,1,3,1,7,6,4}
···

数组中最大的接连的矩形区域的面积为: 12

经博主自个儿亲自测验,该算法可以符合规律的劳作。 🙂

优化部分

共谋优化部分,首先大家得以看出的臆想就是最后的那步求结果集数组中的最大值了呢。

确实是的,大家实在能够别的申请叁个变量,来记录到最近甘休的轮次的最大的十二分子矩阵的面积的。然而这一点优化来讲起到的职能不是十分大,时间复杂度也不曾什么相当大的修正。

别的一些,小编觉的能够相比较好的切入点便是对每一个轮次的进行演算的时候加多贰个料定,来支配当前轮次之前是或不是往下循环。假如数组中的成分的内忧外患十分大的话,优化的档期的顺序依旧很准确的。

总结

这一个小算法相比较娇小,独一比较可惜的地点正是光阴复杂度稍微的有一些大了。要是读者在寻求一种时光复杂度十分小的算法的话,请绕道咯。

倘若只是想寻求贰个结果,照旧不错的。至少比暴力方式的谋算功效高多了。

上述就是本文关于Java编制程序数组中最大子矩阵简便解法实今世码的全部内容,希望对大家具备协理。感兴趣的朋友能够持续参照本站别的相关专题,如有不足之处,应接留言提出。多谢朋友们对本站的补助!

本文研讨的机借使Java编制程序数组中最大子矩阵的相干内容,具体介绍如下。
蒙受二个…

  字符串和数组在累积上是看似的,把它们归为同一主旨之下。本文主要介绍三大类难点和它们衍生的标题,以及相应算法。

明天早上刷水题写到一道最大全1星型,于是兴高采烈将一体系有关都复习了二回qwq

     
求解最安卡拉续子数组的内容在《算法导论》那本书上面是作为分治算法的贰个例证来进展教学的,书本上边内容(满含习题)提到了三种缓慢解决这一标题标算法,上边是自家自身行使C++达成这两种艺术的代码和思路放:

  本文首要介绍和斟酌的标题和介绍的算法(点击跳转):

1.最大子段和 

测量检验地方:

Problem:给出一段种类,选出当中一而再且非空的一段使得这段和最大。

Key:f[i]表示以i为极端时的最大子段和,f[i]=max(f[i-1],0)+a[i];ans=max(ans,f[i]);

图片 4图片 5

 1 #include<cmath>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 const int maxn=200009;
 7 int a[maxn],f[maxn];
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13     {
14         scanf("%d",&a[i]);
15     }
16     for(int i=1;i<=n;i++)
17     {
18         f[i]=max(f[i-1],0)+a[i];
19     }
20     int ans=-0x3f3f3f3f;
21     for(int i=1;i<=n;i++)
22     {
23         ans=max(ans,f[i]);
24     }
25     cout<<ans<<endl;
26     return 0;
27 }

Problem#1

 

一、暴力解法

  • 字符串循环移位(左旋转)难点
    • 算法1:“杂技”代码
    • 算法2:块交换
    • 算法3:求逆(推荐)
  • 以字符串散列为例的哈希表
  • 最长重复子连串难点的后缀数组解法
  • 最奥斯汀续子类别
    • 宗旨难题
      • 直白解法
      • O(n2):优消除法与拉长和数组
      • 分治法解法
      • 举目四望解法
      • 外加研讨
    • 相关主题材料
      • 搜寻总和最周边某些数的一而再子连串
      • 数组分段赋值难点
      • 给定长度的最艾哈迈达巴德续子类别
      • 矩阵求最大和子矩阵

2.最大子矩形和(最大加权矩形) 

测验地方:

Problem:给定贰个平头矩阵,求当中叁个即兴大小的子矩形,使该子矩形内值的和最大。

Key:将二维的矩阵按行压成一维,枚举列来做最大子段和,复杂度O(n^3)。

图片 6图片 5

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 const int maxn=150;
 8 int a[maxn][maxn],n,m,sum[maxn];
 9 int ans=-0x3f3f3f3f;
10 int f[maxn];
11 int calc_max(int val[],int n)
12 {
13     int ret=-0x3f3f3f3f;
14     f[1]=val[1];
15     for(int i=2;i<=n;i++)
16         f[i]=max(f[i-1],0)+val[i],ret=max(ret,f[i]);
17     return ret;
18 }
19 
20 int main()
21 {
22     scanf("%d",&n);
23     m=n;
24     for(int i=1;i<=n;i++)
25     {
26         for(int j=1;j<=m;j++)
27         {
28             scanf("%d",&a[i][j]);
29         }
30     }
31     for(int i=1;i<=n;i++)
32     {
33         for(int k=1;k<=m;k++)
34         {
35             sum[k]=0;
36         }
37         for(int j=i;j<=n;j++)
38         {
39             int k;
40             for(k=1;k<=m;k++)
41             {
42                 sum[k]+=a[j][k];
43             }
44             int mx=calc_max(sum,k);
45             ans=max(ans,mx);
46         }
47     }
48     cout<<ans<<endl;
49     return 0;
50 }

Problem#2

 

     
对数组内每二个数A[i]张开遍历,然后遍历以它们为源点的子数组,相比较各种子数组的高低,找到最阿比让续子数组

 

3.最大全1正方形

测验地方:

Problem:在一个n*m的只包蕴0和1的矩阵里寻觅三个不满含0的最大星型,输出边长。

Key:

  解法1:暴力体贴二维前缀和,枚举边长来更新ans,其中求二维前缀和是容斥原理。

图片 8图片 5

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<algorithm>
 6 using namespace std;
 7 const int maxn=109;
 8 int n,m,sum[maxn][maxn],ans=0;
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     for(int i=1;i<=n;i++)
13     {
14         for(int j=1;j<=m;j++)
15         {
16             int x;
17             scanf("%d",&x);
18             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
19         }
20     }
21     for(int i=1;i<=n;i++)
22     {
23         for(int j=1;j<=m;j++)
24         {
25             for(int l=1;l+i<=n&&l+j<=m;l++)
26             {
27                 int ok=sum[i+l][j+l]-sum[i+l][j]-sum[i][j+l]+sum[i][j];
28                 if(ok==l*l)
29                 {
30                     ans=max(ans,l);
31                 }
32             }
33         }
34     }
35     printf("%d",ans);
36     return 0;
37 }

Problem#3–解法1

  解法2:f[i][j]代表以(i,j)为右下角的时候,能拉开左上角到最大的的正方形。借使(i,j)那一个点为0时直接不考虑,不为0时才总括转移方程f[i,j]=min(f[i-1,j-1],f[i-1,j],f[i,j-1]),转移方程的实际意义是右上方、左方、右方能扩张的最大边长+1
(加1的操作正是一个钱打二十五个结(i,j)自个儿)。

图片 10图片 5

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 const int maxn=109;
 8 int f[maxn][maxn],n,m,ans=0;
 9 int main()
10 {
11     scanf("%d%d",&n,&m);
12     for(int i=1; i<=n; i++)
13     for(int j=1; j<=m; j++)
14     {
15         int x;
16         scanf("%d",&x);
17         if(x)//如果这一个格子是1
18         {//f[i][j]表示以(i,j)为右下角的,能延伸左上角最大的(正方形)边长
19             f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
20             //取min是为了验证是不是三个格子都能达到扩展要求
21             //如果其中一个值为0,说明那个角没法扩展正方形
22             //如果其中最小值为x,说明这个点最多扩展x,加他自己就是+1
23             ans=max(ans,f[i][j]);
24         }
25     }
26     cout<<ans<<endl;
27     return 0;
28 }

Problem#3–解法2

 

#include "stdafx.h"
//暴力法求最大子数组和问题
int _tmain(int argc, _TCHAR* argv[])
{
    int A[8] = { -6, 10, -5, -3, -7, -1, -1 };
    int array_length = sizeof(A) / sizeof(A[0]);//数组大小
    int sum = -10000;//记录子数组的和
    int low;//记录子数组的底
    int height;//记录子数组的高
    for (int i = 0; i < array_length; i++)
    {
        for (int j = i ; j < array_length; j++)
        {
            int subarraysum=0;//所遍历出来的子数组的和
            //计算遍历的子数组之和
            for (int k = i; k <= j; k++)
            {
                subarraysum += A[k];
            }
            //找出最大的子数组
            if (subarraysum>sum)
            {
                sum = subarraysum;
                low = i;
                height = j;
            }
        }
    }
    printf("%d  %d  %d", low, height,sum);//将结果打印出来
    getchar();
    return 0;
}

4.最大全1矩形

测量试验地点:

Problem:给出1个M*N的矩阵M1,里面包车型的士要素唯有0或1,寻找M1的叁个子矩阵M2,M第22中学的成分独有1,况且M2的面积是最大的。输出M2的面积。

Key:

  解法1:存款和储蓄矩阵时,将非1的要素存成-inf,直接做一遍最大子矩形和。

  解法2:管理每一行的每种要素能向下延长的最大全1长短,那样获得每一行都以二个方可“histogram求最大矩形”的行列。首要做法是对于每一行,从左到右遍历一回刚刚收获的连串,用f[i]表示以i为起源时,向右能扩展的最大矩形面积,最后在装有的f数组中取max。

  解法3:递推管理,f[i][j]代表第i行,第j列时,从i能延伸的最大全1长短。记录l和r五个数组,分别表示能向左或右扩充的最大职分。

图片 12图片 5

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 const int maxn=1009;
 7 int l[maxn],r[maxn];
 8 int f[maxn][maxn],n,m;
 9 int main()
10 {
11     
12     scanf("%d%d",&n,&m);
13     for(int i=1; i<=n; ++i)
14         for(int j=1; j<=m; ++j)
15         {
16             int x;
17             scanf("%d",&x);
18             if(x==1)f[i][j]=f[i-1][j]+1;
19             else f[i][j]=0;
20         }
21     int ans=0;
22     for(int i=1; i<=n; ++i)
23     {
24         for(int j=1; j<=m; ++j)
25             l[j]=r[j]=j;
26         f[i][0]=f[i][m+1]=-1;
27         for(int j=1; j<=m; ++j)
28         {
29             while(f[i][j]<=f[i][l[j]-1])
30                 l[j]=l[l[j]-1];
31         }
32         for(int j=m; j>=1; --j)
33         {
34             while(f[i][j]<=f[i][r[j]+1])
35                 r[j]=r[r[j]+1];
36         }
37         for(int j=1; j<=m; ++j)
38         {
39             if(f[i][j])
40             {
41                 int t=(r[j]-l[j]+1)*f[i][j];
42                 if(t>ans)ans=t;
43             }
44         }
45     }
46     printf("%d\n",ans);
47     return 0;
48 }

Problem#4–解法3

 

可以见见这段程序里面一共嵌套着三层循环,除了最外面包车型大巴循环会循环n次外内部的循环都比n次小,此程序的时日复杂度为O(n3

字符串循环移位(左旋转)难题

主题素材叙述:

  将二个n元一维向量向左旋转i个岗位。举例,当n=8且i=3时,”abcdefgh”旋转为”defghabc”,供给时间为O(n),额外部存款和储蓄器储占用为O(1)。(《编制程序珠玑》第二章难题B)

分析:

  严酷来讲这并非贰个字符串,因为’\0’是不会活动的。为了陈诉方便,能够把它认为是字符串,只是不对’\0’实行操作罢了。

  就算不思量时间要求为O(n),那么能够每趟全体左移一个人,一共移动i次。只使用O(1)的空中的标准化下,一共要开始展览成分沟通O(n*i)次;

  借使不思考空间供给为O(1),那么能够把前i个存入有的时候数组,剩下的左移i位,再把偶然数组里的内容放入后i个岗位中。

  很惋惜,由于五个限制条件,以上三种思路都不满意须求。

  对于算法1和算法2,假设知道有窘迫,不必强求,能理解算法3就好。

 

算法1:“杂技”代码

  为了满足O(1)空间的范围,再三再四第三个思路,即使每一遍直接把原向量的叁个因素移动到指标向量中它的应当出现新岗位上就行了。先把array[0]保存起来,然后把array[i]移动到array[0]上,array[2i]移到array[i]上,直至再次来到取原先的array[0]。但那要求消除的题目是,如何保险全数因素都被移位过了?数学上的结论是,依次以array[0],…,array[gcd(i,n)-1]为首元进行巡回就能够,在那之中gcd(a,b)是a与b的最大公约数。由此算法可写为:

图片 14图片 5

int vec_rotate(char *vec,int rotdist, int length) {
    int i,j,k,times;
    char t;
    times = gcd(rotdist,length);
    printf("%d\n",times);
    for(i=0;i<times;i++) {
        t = vec[i];
        j = i;
        while(1) {
            k = j+ rotdist;
            if(k>=length)
                k-=length;
            if(k==i)
                break;
            vec[j] = vec[k];
            j = k;
        }
        vec[j]=t;
    }
    return 0;
}

向量左旋算法1:”杂技”代码

  正如“杂技”一词所暗指的同样,那个算法就像是在玩杂耍球,你要让它们中的每三个都在伏贴的岗位上,这个球,除了手中有三个,别的几个都在上空。假如目生,很轻便手忙脚乱,把球掉的处处都是。

 

算法2:块交换

  思量第1个思路,也就是把向量x分为两片段a和b,左移正是把ab产生ba,当中a包蕴了前i个要素。若是a比b短,把b分为bl和br,那么须要先把a与br交流得到brbla,再对brbl递归左旋。而a比b长的情况周围,当a与b长度相等时一贯两两交流成分就能够成功。同不经常候能够见到,每一遍待沟通的向量长度都自愧比不上上一遍,最后递归甘休。

图片 16图片 5

int vec_rotate_v1(char *vec,int i, int length)
{
    int j = length - i;
    if(i>length)
        i = i%length;
    if(j==0)
        return 0;
    else if(j>i) {
    //case1: ab -> a-b(l)-b(r)
        swap(vec,0,j,i);
        vec_rotate_v1(vec,i,j);
    }    
    //case2: ab -> a(l)-a(r)-b
    //i becomes less
    else if(j<i)    {
        swap(vec,i,2*i-length,j);
        vec_rotate_v1(vec,2*i-length,i);
    }
    else
        swap(vec,0,i,i);
    return 0;
}

int swap(char* vec,int p1,int p2, int n) {
    char temp;
    while(n>0) {
        temp    = vec[p1];
        vec[p1] = vec[p2];
        vec[p2] = temp;
        p1++;
        p2++;
        n--;
    }
    return 0;
}

向量左旋算法2:块调换

  那些算法的弱项是,必要对二种状态实行座谈,并且下标稍不放在心上就能出错。

 

算法3:求逆(推荐)

  三番两次算法2的笔触,并假定有三个支援函数能对向量求逆。那样,分别对a、b求逆获得arbr,再对总体求逆便拿走了ba!难怪小编也要称之为“灵光一闪”的算法。大概在此以前接触过矩阵运算的读者对此极快便能明了,因为(ATBT)T
= BA。算法如下:

图片 18图片 5

int vec_rotate_v2(char *vec,int i,int length){
    assert((i<=0)||(length<=0))
    if(i>length)
        i = i%length;
    if (i==length) {
        printf("i equals n. DO NOTHING.\n");
        return 0;
    }
    reverse(vec,0,i-1);
    reverse(vec,i,length-1);
    reverse(vec,0,length-1);
    return 1;
}

int reverse(char *vec,int first,int last){
    char temp;
    while(first<last){
        temp = vec[first];
        vec[first] = vec[last];
        vec[last] = temp;
        first++;
        last--;
    }
    return 0;
}

向量左旋算法3:求逆

  假使能想到,算法3属实既敏捷,也难以在编写时出错。有人曾主持把这一个求逆的左旋方法当做一种常识。

  来拜候这种思维的应用吧:

扩充:(google面试题)用线性时间和常数附加空间将一篇作品的保有单词倒序。

譬喻:This is a
paragraph for test

处理后: test for
paragraph a is This

假如选拔求逆的方法,先把全文全部求逆,再依据空格对各种单词内部求逆,是或不是一点也不细略?另外Taobao二〇一三年的实习生笔试有道题是近乎的,管理的对象范围比那一个扩大中的“一篇小说”小非常多,当然解法是大旨同样的,只不过分隔符不是空格而已,这里就不重述了。

 


二、分治法