之前在日志中总结了一维最大子段和问题(http://www.stackpop.org/blog/html/y2011/381_max_interval.html)，这次，我们总结一下二维最大子段和问题，以及最大m段和问题.

二维最大子段和问题

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

问题分析

子矩阵的概念这里不再赘述，不了解的可以去复习一下线性代数.如下图所示的
阅读全文 »

几日前在微博上和清华一博士讨论起一道数据结构选择题，我非常信心满满地给出了答案并且以为是对的，却发现和他给的标准答案相去甚远，去wiki和NIST网站查了一下才知道，原来中国大陆教材中的定义和美国以及我国港澳台地区是完全不同的.本科时用的数据结构教材虽然也是国外的，但是由于当时学习没有注意这些概念，之后就受考研时国内教材和考试的荼毒太深了.

满二叉树

国内定义

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树.

严蔚敏《数据结构(C语言版)》124页

阅读全文 »

最大子段和问题(Maximum Interval Sum) 经典的动态规划问题，几乎所有的算法教材都会提到.本文将分析最大子段和问题的几种不同效率的解法，以及最大子段和问题的扩展和运用.

一.问题描述

给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].
阅读全文 »