当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

Java获取子数组的最大和算法

发表于: 2012-01-31   作者:燈小嗨   来源:转载   浏览次数:
摘要:   来源:http://zhedahht.blog.163.com/blog/static/254111742007219147591/ 题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数

 

来源:http://zhedahht.blog.163.com/blog/static/254111742007219147591/

题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18

解决思路:

如果前几项数值累加的结果为负,则可以将这几项排除,因为负数累加后肯定会使总值减少。因此算法分别从左往后和从右往左计算相邻两个数的累加和,当大于零时继续累加,小于零时将之前的累加值清零,从后一个数字开始重新计算。当左右两边指针相遇时,将两边汇总值累加,既为最终结果。

package maxchildarray;

/**
 * 子数组的最大和
 * @author DHC
 *
 */
public class MaxChildArray {

	public static void main(String[] args) {
		// 初始数组
		int[] intArray = {1, -2, 3, 10, -4, 7, 2, -5};
		
		int left = 0; // 从左边开始计算
		int leftTemp = 0; // 左边现在指向的位置
		int leftSum = 0; // 左边的总和
		
		// 右边变量,同上
		int right = intArray.length - 1;
		int rightTemp = intArray.length - 1;
		int rightSum = 0;
		
		// 最终总和
		int sum = 0;
		
		while(true) {
			// 从左往右计算,每次往后移动一位
			if (leftSum + intArray[leftTemp] <= 0) {
				leftTemp++;
				left = leftTemp;
				leftSum = 0;
			} else {
				leftSum += intArray[leftTemp];
				leftTemp++;
			}
			
			// 从右往左计算,每次往前移动一位
			if (rightSum + intArray[rightTemp] <= 0) {
				rightTemp--;
				right = rightTemp;
				rightSum = 0;
			} else {
				rightSum += intArray[rightTemp];
				rightTemp--;
			}
			
			// 前后相遇时进行相应处理
			if (rightTemp - leftTemp == -2) {
				sum = leftSum + rightSum - intArray[rightTemp];
				break;
			} else if (rightTemp - leftTemp == -1) {
				sum = leftSum + rightSum;
				break;
			}
		}
		
		System.out.print("The Max Child Array is : ");
		for (int i = left; i <= right; i++) {
			System.out.print(intArray[i] + " ,");
		}
		System.out.println("\nSummery is " + sum);
	}

}

 练习心得:

其实算法有些时候并没有想象中的这么困难,只要自己静下心来,仔细思考内在的联系应该会有思路的。

另外感觉有了思路后用程序实现过程中会遇到很多细节的问题,这就更要想清楚了。

此算法还有另外一个思路,就是仍然从左边开始遍历,在这个过程中记录一个当前子数组的最大值,前几项小于零时则刷新所有数据,从后面一个数重新开始,当发现累加结构大于记录的最大值时,则替换,最后比较完后,记录的最大值就为真实的最大值。这种算法,只用从左边开始遍历数组,而且避免了两边同时遍历相遇时的一些处理,应该说比上面代码实现的算法更加简单,http://zhedahht.blog.163.com/blog/static/254111742007219147591/,这篇博文用C实现了这个简洁的算法。

Java获取子数组的最大和算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
连续子数组的最大和 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 输入一个整型数
题目: 输入一个整型数组,数据元素有正数也有负数,求元素组合成连续子数组之和最大的子数组,要求
题目: 输入一个整型数组,数据元素有正数也有负数,求元素组合成连续子数组之和最大的子数组,要求
/* * MaxSumSubArray.cpp * * Created on: 2012-6-20 * Author: jiyiqin * * 给定一个包含正数,负
求数组子序列的最大和 一、问题描述 输入一个整形数组,数组里可以有正数或负数。数组中连续的一个
注意:当函数输入无效时,返回为0,而子数组的和也有可能为0,为了区分,设置一个全局变量标记输入
本文内容框架: §1 连续子数组最大和 基本方法、分治策略求解、动态规划求解 §2 最长递增子序列 排
注意:当函数输入无效时,返回为0,而子数组的和也有可能为0,为了区分,设置一个全局变量标记输入
题目:求子数组的最大和 要求:1、输入一个整形数组,数组里有正数也有负数。 2、数组中连续的一个
问题描述 给定(可能是负的)整数序列A1, A2,...,AN, 寻找(并标识)使Sum(Ak)(k >=i, k <= j
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号