打破思维断层之最大子序列和

         最大子序列和

目的：

本博客以求最大子序列和算法为载体，试图在减少思维断层的情况下解决问题。

目录：(以全新视角审视本问题)

      1)问题阐述
      2)问题本质
      3)代码实现

第一步：问题阐述

        一个有N个元素的整型数组A，有正有负，数组中连续一个或多个元素组成一个子数组，这个数组有很多子数组，求子数组之和的最大值。

 

        例如：[1，-2，3，5，-1,-1,  3]的最大子序列[3,5,-1,-1,3].

                        [-9，-2，-3，-5，-3, -1]的最大子序列[-1]

 

        （注：定义中要求的是连续的，其实这个问题的名称很不称职，“子序列”这个名字其实意味着并不要求各个元素相连，像最长公共子序列（LCS）问题中一样，并没有要求连续。所以这个问题另外一个名字较好：最大字数组和。）

 

第二步：问题本质

        下面我们来想一下这个问题，也许最简单的办法就是把所有的子数组全部求出来，然后比较选出最大的一个。
        相信网上有很多代码实现，最差的o(n3) ,优化过后可以是o(n2).（优化的依据是找出最大的，并不需要保存所有的子数组），最优美的应该是动态规划方法。但是通过分析问题知道此问题确实包含最优子结构和重叠子问题，但是实现起来还是有些困难，总觉的有些东西没想明白，于是仔细分析该问题的本质之后才豁然开朗。

        下面来分析此问题的本质：用图片表示

        单纯的看这个简单的题目，也许很多人能够直接给出答案最大字数组和是8即3+5.如果数组元素很多，事情就难办了，这个问题最好状态下时间复杂度是多少呢？是o（n）

        原因在于：本例中我们先是算出[1,1] = 1, [1,2] = 3,[1,3] = -1.事情就在这里发生了转折，因为我知道，下一步很多子数组已经被淘汰了，无需计算。这些无需计算的字数组是前3列。为什么呢？

 

 

 之后我们分别计算了[4,4]，[4,5]和[4,6]

这样我们就真的做到了o(n)

其实很多博客提到了全是负数的情况，我们举例证明

最大值是:-1,时间复杂度仍旧是o（n） 

 第三步：代码实现

       上述分析如何用代码迅速实现呢？还是以上面例子分析

        开始我们计算[1,1],[1,2],[1,3]这个可以使用两个指针i和j 。i和j开始同时指向1，i不变，j不断增加，当增加到3的时候，发现总的大小小于0，此时意味着j不需要在增大为4，5，6（第一列无需再计算） i重新赋值为j+1 =4 （前j列不需再计算）

 

/**
	 *  最大子序列和
	 * @param data
	 * @return
	 */
	public static int maxSubarray(int[] data) {
		//保存真正最大子序列和的起始位置
		int start = 0;
		int end = 0;
		//最大值
		int max = Integer.MIN_VALUE;

		//当前序列起始位置和最大值
		int currentStart = 0;
		int currentEnd = 0;
		int currentMax = 0;
		//
		for (int i = 0; i < data.length; i++) {
			currentMax += data[i];
			//判断当前是否大于0
			if (currentMax >= 0) { 
				currentEnd = i;
				if (currentMax > max) {
					max = currentMax;
					start = currentStart;
					end = currentEnd;

				}
			} else {
				currentMax = 0;
				currentStart = i + 1;
				currentEnd = i + 1;
			}
		}
		//打印结果
		for (int i = start; i <= end; i++) {
			System.out.println("i = " + i + "  " + data[i]);
		}
		System.out.println("max = " + max);
		return max;
	}

 多提意见.....

评论

2 楼 十三月的 2013-04-18  

akandfxs 写道

[1，-2，3，5，-1,-1,  3]的最大子序列[3,5,-1,-1,3]

抱歉 写错了，已经改正

1 楼 akandfxs 2013-04-18  

[1，-2，3，5，-1,-1,  3]的最大子序列[3,5,-1,-1,3]