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

java-3.求子数组的最大和

发表于: 2012-01-12   作者:bylijinnan   来源:转载   浏览:
摘要: package beautyOfCoding; public class MaxSubArraySum { /** * 3.求子数组的最大和 题目描述: 输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4,
package beautyOfCoding;


public class MaxSubArraySum {

	/**
	 * 3.求子数组的最大和
题目描述:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
下面的解法:数组元素全是负数时,认为子数组最大和为0
	 */
	
	public static void main(String[] args) {
		int[] a={-1,-2,-3,-10};
//		int[] a={1, -2, 3, 10, -4, 7, 2, -5};
		maxSubArraySum3(a);
		maxSubArraySum2(a);
		maxSubArraySum(a);
	}

	/*2012-07-29 编程之美书上的这个分析比较好理解,因此我写了maxSubArraySum2。其实maxSubArraySum2可以轻易地转换成maxSubArraySum。这两个方法本质是一样的。
假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j],则有以下3种情况
1)当0=i=j的时候,元素A[0]本身构成和最大的一段
2)当0=i<j的时候,和最大的一段以A[0]开头
3)当0<i时候,元素A[0]跟和最大的一段没有关系
Start[i]表示从第i个元素开始(包括第i个元素)的子数组和最大值,All[i]表示A[i]A[i+1]...A[n-1]这个数组的子数组和的最大值
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
	 */
	static void maxSubArraySum2(int[] a){
		//略去参数检查
		int Start=0;
		int All=0;
		for(int i=0,len=a.length;i<len;i++){
			All=max(a[i],Start+a[i],All);
			Start=max(a[i],a[i]+Start);		//if start<0, start=a[i]
		}
		System.out.println("maxSubArraySum="+All);
	}
	
	static int max(int x,int...y){
		int max=x;
		for(int i:y){
			if(i>max){
				max=i;
			}
		}
		return max;
	}
	
	static void maxSubArraySum(int[] a){
		int len=a.length;
		int sum=0;
		int max=0;
		int lastIndex=-1;
		for(int i=0;i<len;i++){
			if(sum<=0){
				sum=a[i];
			}else{
				sum+=a[i];
			}
			if(sum>max){
				max=sum;
				lastIndex=i;
			}
		}
		System.out.println("maxSubArraySum="+max);
		if(lastIndex!=-1){
			System.out.println("and the subArray is:");
			//print the sub array
			int i=lastIndex;
			while(i>=0&&sum>=0){
				sum-=a[i];
				i--;
			}
			for(int j=i;j<=lastIndex;j++){
				System.out.print(a[j]+" ");
			}
		}
		
	}
	
	/*下面这个方法是编程之美里面在讲二维数组的子数组最大和时候提到的:
p[0]=a[0],
p[i]=p[i-1]+a[i]=a[0]+a[1]+...a[i],1<=i<=(n-1)
那么
a[i]+a[i+1]+...a[j]=p[j]-p[i-1]
子数组和最大值为max(p[j]-p[i]),0<=(i,j)<=(n-1)
	 */
	static void maxSubArraySum3(int[] a){
		//略去参数检查
		boolean allNegative=true;
		int len=a.length;
		int[] p=new int[len];
		for(int i=0;i<len;i++){
			if(allNegative){
				if(a[i]>0){
					allNegative=false;
				}
			}
			if(i==0){
				p[0]=a[0];
			}else{
				p[i]=p[i-1]+a[i];
			}
		}
		if(allNegative){
			System.out.println("maxSubArraySum=0");
		}else{
			int max=p[0];
			int min=p[0];
			for(int i=0;i<len;i++){
				if(p[i]>max){
					max=p[i];
				}
				if(p[i]<min){
					min=p[i];
				}
			}
			System.out.println("maxSubArraySum="+(max-min));
		}
		
	}
}

java-3.求子数组的最大和

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:求子数组的最大和 要求:1、输入一个整形数组,数组里有正数也有负数。 2、数组中连续的一个
题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个
这是前几天遇见的一个笔试题。到网上收了一下,也有而且还给出了代码实现。参考了v_JULY_v的 不过我
输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组
一个有n个整数元素(可以是负数)的一维数组,连续的子数组有很多,那连续的子数组之和的最大值是什
一 问题: 输入一组数据,有正数和负数,数组中连续的一个或多个整数组成一个子数组,每个子数组都有
看《编程珠玑》看的郁闷毁了~ 木有激情啊~ 这里描述第8章的一道题:求子串最大和: 一个具有n个浮点
求子串最大积 问题: 给定一个长度为N的整数数组, 只允许用乘法, 不能用除法, 计算任意 (N-1)
/* * MaxSumSubArray.cpp * * Created on: 2012-6-20 * Author: jiyiqin * * 给定一个包含正数,负
面试的时候已经不是第一次遇到这个问题,该问题的解法也非常的多,穷举,分治,DP,扫描,复杂度也
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号