分类目录归档：程序相关

C,Python,环境配置等

算法设计技术：一维模式识别

算法设计技术：一维模式识别
最近重温经典《编程珠玑》，在第8章算法设计技术中一维模式识别实例，书中举出了5种不同的解法，解法不断优化，不断的变得高效，不断得变得更优雅，看完感触良深。已经三年没有和算法有过直接沟通了，也淡忘了，从记忆中唤起，再次遇到，发现有些思想已经深入到骨子里了。
回正题。
【问题描述】
输入n个数的序列，输出这n个数的任意连续子序列的最大和。在这里我们假设序列的数都为整数（包括正和负）
如序列： 31 -41 59 26 -53 58 97 -93 -23 84
从[2..6]的总和187为最大

【解法一：穷举法】
最简单的方法，穷举法：即对所有满足0 <= i <= j < n 的(i, j)整数对进行迭代。对于每个整数对，程序都要计算x[i..j]的总和，并检验该总和是否大于迄今为止的最大总和。其PHP实现如下：

<?php
/**
 * 一维模式识别算法一，穷举法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	for ($i = 0; $i < $len; $i++) {
		for ($j = $i; $j < $len; $j++) {
			$sum = 0;
			for ($k = $i; $k <= $j; $k++) {
				$sum += $seq[$k];
			}
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

算法一优点是非常清晰明了，一眼就看出其思路，并且实现简单。
但是其时间复杂度为O(n的立方)，如果数据量稍微大一点，整个程序的效率将会巨慢。

【解法二：】
x[i..j]的总和与前面已计算的总和x[i..j-1]密切相关，即x[i..j] = x[i..j-1] + x[j]
于是我们有了解法二。
如下所示PHP代码：

<?php
/**
 * 一维模式识别算法二，穷举法的优化算法，将时间复杂度变为n的平方
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	for ($i = 0; $i < $len; $i++) {
		$sum = 0;
		for ($j = $i; $j < $len; $j++) {
			$sum += $seq[$j];
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

【解法三：预处理】
同样是根据x[i..j]的总和与前面已计算的总和x[i..j-1]密切相关，即x[i..j] = x[i..j-1] + x[j]
不过我们使用另外一种表示：预处理数据，计算cumarr[i] = x[0..i]，则x[i..j] = cumarr[j] – cumarr[i - 1]
然后再如解法二一样遍历比较，算出最大的值。
如下所示代码：

<?php
/**
 * 一维模式识别算法三，穷举法的优化算法，将时间复杂度变为n的平方
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$len = count($seq);
 
	/* 预处理数据 */
	$cumarr[-1] = 0;
	for ($i = 0; $i < $len; $i++) {
		$cumarr[$i] = $cumarr[$i - 1] + $seq[$i];
	}
 
	for ($i = 0; $i < $len; $i++) {
		for ($j = $i; $j < $len; $j++) {
			$sum = $cumarr[$j] - $cumarr[$i - 1];
 
			if($sum > $maxsofar) {
				$maxsofar = $sum;
			}
		}
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

【解法四：分治算法】
分治原理：要解决规模为n的问题，可递归地解决两个规模近似为n/2的子问题，然后对它们的答案进行合并以得到整个问题的答案。
首先创建两个子序列a和b,然后递归找出a,b中元素总和最大的子向量，分别称为ma和mb，也许我们可能找到最后的解了，可是也有可能答案所在的子序列一部分在ma，一部分在mb，对于这种跨越边界的序列我们将其称之为mc。
我们的分治算法将递归地计算ma和mb，并通过其它方法计算mc，然后返回3个总各和中的最大者。
其PHP实现如下：

<?php
/**
 * 一维模式识别算法四，分治算法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq, $left, $right) {
	if($left > $right) {
		return 0;	//	已没有元素 递归返回
	}
 
	if($left == $right) {
		return max(0, $seq[$left]);	//	只有一个元素，返回这个元素与0之间的较大值
	}
 
	$middle = floor(($left + $right) / 2);
 
	/* 左边从中间开始的最大子序列和 */
	$lmax = $sum = 0;
	for($i = $middle; $i >= $left; $i--) {
		$sum += $seq[$i];
		$lmax = max($lmax, $sum);
	}
 
	/* 右边从中间开始的最大子序列和 */
	$rmax = $sum = 0;
	for($i = $middle + 1; $i <= $right; $i++) {
		$sum += $seq[$i];
		$rmax = max($rmax, $sum);
	}
 
	return max($lmax + $rmax, maxsofar($seq, $left, $middle), maxsofar($seq, $middle + 1, $right));
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq, 0, count($seq) - 1);
die();

对于mc的计算，通过观察发现，mc在a中包含右边界的最大子序列，而mc在了中包含左边界的最大子序列
此解法的时间复杂度为O(nlogn)

【解法五：扫描算法】
最大总和的初始值设为0，假设我们已解决了x[0..i-1]的问题，那么最大总各子序列要么在前i-1个元素中，要么其结束位置为i

<?php
/**
 * 一维模式识别算法五，扫描算法
 * @author phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package test
 */
 
function maxsofar($seq) {
	$maxsofar = 0;
	$maxendinghere = 0;
	$len = count($seq);
 
	for($i = 0; $i < $len; $i++) {
		$maxendinghere = max($maxendinghere + $seq[$i], 0);
		$maxsofar = max($maxsofar, $maxendinghere);
	}
 
	return $maxsofar;
}
 
$seq = array(31, -41, 59, 26, -53, 58, 97, -93, -23, 84);
echo maxsofar($seq);
die();

理解这个程序的关键在于变量$maxendinghere。
在循环中的第一个赋值语句之前，$maxendinghere是结束位置为i-1的最大子序列的和；赋值语句将其改为结束位置为i的最大子序列的和。
其时间复杂度为O(n)，对于这种时间复杂度为O(n)的算法，一般称其为线性算法。

【后记】
从立方算法到线性算法，这是一个质的飞跃。
虽然现在的工作中可能用不到算法，但是在写程序的过程中能够不自觉的优化自己的代码，这也是一种好的习惯。
《编程珠玑》值得多看几次。

从Facebook与Google Adwords代码想到的

6条回复

从Facebook与Google Adwords代码之间的差距想到的
缘起：
最近缠绵于Facebook与Google之间。需要写Facebook插件，需要写adwords相关程序，对比之下，就有了如下的文字。

话说如何创建Facebook应用，可以参照Facebook App开发或官方文档。

下面就如下几个方面对比下两边的代码：

文件结构

Facebook是三个文件和一堆在线的文档。在这三个文件有包含测试驱动的文件，一个很简单的示例，一个我们可以调用的简单sdk。给人的感觉，很随意。
Google是一个压缩包，包括N个文件夹和N层的结构，其中包括针对每个实体每个服务的详细示例，包括测试数据等等。给人的感觉，很专业。

代码规范

我们可以看到google的代码有严格按照代码规范来写，对每个文件有详细的注释（在头部可能有超过30行的注释），空格等都比较注意，根据其注释是可以生成相关的说明文档的。
Facebook的核心代码只有一个文件，针对每个函数都有注释，但是在空格，访问控制说明方面有所欠缺（换句话说，它的规范与我理解中的规范不一样）。也许是其不需要这样，因为仅仅有一个文件。

程序示例

facebook的示例是一个很简单的登录示例。在其官网上有很多在线的帮助文档，只是也仅仅只有程序员会去看一个产品的帮助文档，相对于一个好的示例，或者一些完整一点的示例，我相信大多数人都会选择看示例，而不是文档。
Google对于每个实体都会有相对应的实例，开发人员可以在这个基础上直接修改代码，从而达到自己的目的。另外在其站点上也有详细的说明文档，包括各个参数的说明等等。

可能此时会有人说了，adwords是要付钱的，facebook是不要钱

是的，事实是这样的，可以在某些时候，我们需要看到细节决定成败。

另外：在示例或者帮助说明这块，omniture做得很好，不仅有帮助文档还有omniture大学，omniture视频等等

在这里，我们假设Facebook的代码是一个新手写的，Adwords的代码是一个老手写的，此时就引出了另一个问题—经验值多少钱，就国内的形势，程序员到一定的年龄就考虑转型，对比其它行业，一个人在一个领域专注至少10年，20年，最后才是专家，而在程序这块，5年，8年，不得了，算得上写了很长时间了。

此后，何去何从？

年轻无极限，成长是要付出代价的。
最近浮躁了，也该淡定下

以上只是一个写完程序的程序员在休息时候的胡思乱想，仅此而已！

附：最近看财经郎眼，看郎教授暴粗口，很爽！

最小矩阵和

2条回复

很久很久以前的代码，在某个角落找到，贴了上来，
在杭电acm1081上可以ac，来源应该是Greater New York 2001
貌似作为中南赛区ACM竞赛题

问题描述
【Description】

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

is in the lower left corner:

9 2
-4 1
-1 8
and has a sum of 15.

【Input】

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

【Output】

Output the sum of the maximal sub-rectangle.

【Sample Input】
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

【Sample Output】
15

下面的中文来自：http://blog.csdn.net/hym666/archive/2010/08/17/5818591.aspx
此文章处有C++的解答

题目描述：
在一个大的方阵中找出一个子方阵，这个子方阵是所有子方阵和中的最大的一个
问题分析：
问题可以回归到一个数列中的连续字数列的和的最大值。
即把每一行看成一个数列。把每一列转换成一个数。
当然每一列也是一个数列，有很多的连续子数列。所有会有很多中情况。可穷举各种数列来构造一个行向的数列。
再用动态规划计算每一行的最大值，再在各行中选取最大的作为题目的解。

【代码】

import java.util.*;
 
public class Main {
 
       /**
        * @param args
        */
 
       public static int maxSum(int[] b, int n){
 
              int max = b[0], sum = 0;
 
              for (int i = 1; i < n ; i++ ){
                     if (max > 0)
                            max += b[i];
                     else
                            max = b[i];
 
                     if (max > sum)
                            sum = max;
              }
              return sum;
       }
 
       public static int maxTotal(int[][] a, int n){
 
              int max = 0;
              int[] b = new int[n];
 
              for (int i = 0; i < n; i++){
                     for (int j = 0; j < n; j++)
                            b[j] = a[i][j];
 
                     int sum = maxSum(b, n);
 
                     if (sum > max)
                            max = sum;
 
                     for (int j = i + 1; j < n; j++){
                            for (int k = 0; k < n; k++)
                                   b[k] += a[j][k];
 
                            sum = maxSum(b, n);
                            if (sum > max)
                                  max = sum;
                     }
              }
              return max;
       }
 
       public static void main(String[] args) {
              // TODO Auto-generated method stub
 
              Scanner cin = new Scanner(System.in);
              int n;
 
              while (cin.hasNext()){
                     n = cin.nextInt();
                     int[][] a = new int[n][n];
                     for (int i = 0; i < n; i++){
                            for (int j = 0; j < n; j++){
                                   a[i][j] = cin.nextInt();                                  
                            }
                     }
                     System.out.println(maxTotal(a, n));
              }
       }
}

潘锦的空间

SaaS SaaS架构团队管理技术管理技术架构 PHP 内核扩展项目管理

分类目录归档：程序相关

算法设计技术：一维模式识别

从Facebook与Google Adwords代码想到的

最小矩阵和