首页 > 代码库 > 二维数组的最大子串和
二维数组的最大子串和
先有一个概念:部分和:ps[i][j]表示从(0,0)到(i,j)这个矩形的和,那么有ps[i][j] = ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+a[i][j],从而可以在o(m*n)的时间内求出ps
这样有了ps后,就可以在o(1)时间内求出(i,j)到(p,q)这个矩形的和了,即 ps[p][q] - ps[i][j]
第一种方法:如果遍历所有可能的矩形,那么需要o(n*n*m*m)的时间
//枚举上下左右的边界值for il in 0..n for ir in il+1..n for jl in 0..m for jr in jl+1..m Max = max(Max,ps[ir][jr] - ps[il][jl])
第二种方法:考虑一维化。
* * * * *
* * * * * p 把这这个红色矩形的一列的和看做一个数
* * * * *
* * * * *
* * * * * q
* * * * *
* * * * *
比如当确定上下边界 p,q 的时候,把a[p][i]..a[q][i]看为一个数,这样就是求一个一维数组的最大子串和了,需要O(m)的时间,所以最终需要 O(n*n*m)的时间,优化比较m和n的大小看是从左到右扫还是从上到下扫,优化为o(m*n*min(m,n))
如果是环状的二维数组呢???嘿嘿,任然考虑一维的那种情况~~~最大和最小是相对的,然后求普通数组的最小,用总和减去它就得到环状的最大。最后比较环状的最大和普通的最大就可以了。
二维数组的最大子串和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。