美文网首页
坐标型-- ( c ) 递推每个格子的属性

坐标型-- ( c ) 递推每个格子的属性

作者: simboter | 来源:发表于2019-02-10 14:28 被阅读0次
1) maximal square (LeetCode 221)
[要求] 找出0,1矩阵中最大的全1正方形
[定义格子A[i][j]的某种属性] 以本格A[i][j]收尾(右下角)的最大正方形的边长,用f[i][j]表示
[图释]
[复杂度] 时间 O(n * m), 空间 O(n * m)

2) maximum product subarray (LeetCode 152)
[要求] 找出数组的一个子数组,其自乘积最大
[限制] 数组数字有正有负
[定义格子A[i]的某种属性] 以本格A[i]收尾的子数组所能达到的最大乘积和最小乘积,用f[i][0]和f[i][1]表示
[图释]
[复杂度] 时间 O(n), 空间 O(n)

相关文章

网友评论

      本文标题:坐标型-- ( c ) 递推每个格子的属性

      本文链接:https://www.haomeiwen.com/subject/napnsqtx.html