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

java-61-在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差. 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5,

发表于: 2012-02-09   作者:bylijinnan   来源:转载   浏览:
摘要: 思路来自: http://zhedahht.blog.163.com/blog/static/2541117420116135376632/ 写了个java版的 public class GreatestLeftRightDiff { /** * Q61.在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差。 * 求所有数对之差的最大值。例如在数组
思路来自: http://zhedahht.blog.163.com/blog/static/2541117420116135376632/
写了个java版的


public class GreatestLeftRightDiff {

	/**
	 * Q61.在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差。
	 * 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
	 */
	public static void main(String[] args) {
		int[] a={2, 4, 1, 16, 7, 5, 11, 9};
		int result=greatestLeftRightDiff01(a);
		System.out.println(result);
		result=greatestLeftRightDiff02(a);
		System.out.println(result);
		
	}
	/*引用原文:
	 * 如果输入一个长度为n的数组numbers,我们先构建一个长度为n-1的辅助数组diff,
	 * 并且diff[i]等于numbers[i]-numbers[i+1](0<=i<n-1)。
	 * 如果我们从数组diff中的第i个数字一直累加到第j个数字(j > i),
	 * 也就是diff[i] + diff[i+1] + … + diff[j] 
	 * = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... + (numbers[j] – numbers[j + 1])
	 *  = numbers[i] – numbers[j + 1]。
	 *  分析到这里,我们发现原始数组中最大的数对之差(即numbers[i] – numbers[j + 1])
	 *  其实是辅助数组diff中最大的连续子数组之和。
	 */
	public static int greatestLeftRightDiff01(int[] a){
		if(a==null||a.length<2){
			return Integer.MIN_VALUE;//min=1<<31
		}
		int len=a.length;
		int[] diff=new int[len-1];
		for(int i=1;i<len;i++){
			diff[i-1]=a[i-1]-a[i];
		}
		return greatestSumOfSubArray(diff);
	}
	
	/*
	 *1.我的理解:从i=2开始遍历,找出i之前的最大元素,记为max,max减去当前元素a[i],如果这个差值比旧差值大,则更新旧差值
	 *2.引用原文:
	 *我们定义diff[i]是以数组中第i个数字为减数的所有数对之差的最大值。
	 * 也就是说对于任意h(h < i),diff[i]≥number[h]-number[i]。diff[i](0≤i<n)的最大值就是整个数组最大的数对之差。
	 * 假设我们已经求得了diff[i],我们该怎么求得diff[i+1]呢?对于diff[i],肯定存在一个h(h < i),满足number[h]减去number[i]之差是最大的,也就是number[h]应该是number[i]之前的所有数字的最大值。当我们求diff[i+1]的时候,我们需要找到第i+1个数字之前的最大值。
	 * 第i+1个数字之前的最大值有两种可能:这个最大值可能是第i个数字之前的最大值,也有可能这个最大值就是第i个数字。
	 * 第i+1个数字之前的最大值肯定是这两者的较大者。
	 * 我们只要拿第i+1个数字之前的最大值减去number[i+1],就得到了diff[i+1]。
	 */
	public static int greatestLeftRightDiff02(int[] a){
		if(a==null||a.length<2){
			return Integer.MIN_VALUE;//min=1<<31
		}
		int len=a.length;
		int max=a[0];
		int diff=max-a[1];
		for(int i=2;i<len;i++){
			if(max<a[i-1]){
				max=a[i-1];
			}
			int newDiff=max-a[i];
			if(newDiff>diff){
				diff=newDiff;
			}
		}
		return diff;
	}
	
	
	public static int greatestSumOfSubArray(int[] array){
		int sum=0;
		int max=0;
		for(int i=0,len=array.length;i<len;i++){
			sum+=array[i];
			if(sum<=0){
				sum=0;
			}else{
				if(sum>max){
					max=sum;
				}
			}
		}
		return max;
	}
}

java-61-在数组中,数字减去它右边(注意是右边)的数字得到一个数对之差. 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5,

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1.区间是一段的,不是断开的哟 2.代码是看着标程写的 3.枚举左端点,二分右端点流程: #include<
#include <stdio.h> #include <string.h> int next_num(int x) { char s[10]; int a,b,
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
方法1:暴力方法 遍历一遍数组,比较2*N次求出最大值和最小值 方法2:改进方法 (破坏了原数组) 遍
题目要求:给定一个整数数组,其中只有1个数出现1次,其他数字都出现偶数次。找出这个数字。如果其
/* (程序头部注释开始) * 程序的版权和版本声明部分 * Copyright (c) 2011, 烟台大学计算机学院学生
题目: 给定一个整数数组int[] a (a.length > 1),和一个整数值 m,试输出所有运算结果等于m的运
Copyright(c)2013,烟台大学计算机学院学生 *All rights reserved. *文件名称: 数组中的相同数字
我的程序: [cpp] view plain copy print ? /* * 程序的版权和版本声明部分: * Copyright (c) 2011,
转载请注明出处:http://blog.csdn.net/mmc_maodun/article/details/27800577 题目:一个int数组中有
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号