package maxD_value;
/**
* 题目:在数组中,数字减去它右边的数字得到一个数对之差。
* 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
*
*/
public class Test {
//下面这个方法是从后往前遍历一遍,找出最小的值,然后用前面的值减去最小的值,并找出遍历中的最大数,则得到了结果。
public static int maxValue_MethodOne(int array[])
{
int max=0,D_value;
int n = array.length;
int min = array[n-1];
for(int i=n-2;i>=0;i--)
{
D_value = array[i] - min;
if(D_value > max )
// 如果当前的差值比以前的值都大,则更新结果。
max = D_value;
if(D_value<0)
min = array[i];
//如果一个D_value<0 则说明当前的array[i]比min还小,则更改min的值
}
return max;
}
//下面的这种方法和上面的思想是一样的
public static int maxValue_MethodTwo(int array[])
{
int D_value,result=0;
int n = array.length;
int max = array[0];
for(int i=1;i<n;i++)
{
D_value = max - array[i];
if(array[i]>max)
max = array[i];
if(D_value>result)
result = D_value;
}
return 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 maxValue_MethodThree(int array[])
{
//新建一个数组,用于存放原来数组中相邻两个数据的差值
int n = array.length;
int tem[] = new int[n-1];
for(int i=1;i<n;i++)
{
tem[i-1] = array[i-1]-array[i];
}
// 下面就转化为求tem数组中连续字段和最大的问题了,
int max = 0;
int sum=0;
for(int i=0;i<tem.length;i++)
{
sum += tem[i];
if(sum>max)
max = sum;
if(sum<0)
{
sum =0;
}
}
return max;
}
public static void main(String[] args) {
int arr[] = new int[]{2, 4, 1, 16, 7, 5, 11, 9};
System.out.println("求解数组中的差值最大问题\n");
int max = maxValue_MethodOne(arr);
System.out.println("使用第一种方法求解的结果为 :"+max);
max = maxValue_MethodTwo(arr);
System.out.println("使用 第二种方法求解的结果为:"+max);
max = maxValue_MethodThree(arr);
System.out.println("使用第三种方法求解的结果为:"+max);
}
}
运行的结果为:
求解数组中的差值最大问题
使用第一种方法求解的结果为 :11
使用 第二种方法求解的结果为:11
使用第三种方法求解的结果为:11
分享到:
相关推荐
求三数最大值
是c语言的三个数的最大值,是三个整数之间的最大值。输入三个整数,求出最大值1!!!!!!
从键盘或者命令行输入3个数,求这三个数的最大值
用户输入三个数求出其中的最大值.png
数据结构第二章上机作业,张宪超。 已知head为单链表的表头指针,链表中储存的都是整形数据,实现下列运算的递归算法: 1.求链表中最大值 2.求链表中的节点个数 3.求所有整数平均值
# include using namespace std; int max(int i, int j){ // 定义max()函数 if (i>=j) return i; else return j; } ... cout最大数是:"(i, j); //输出提示信息和结果 return 0; }
在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
本程序能实现求任意三个数中的最大值
max函数求4个数最大值
汇编 求一组八位无符号数的最大值、最小值、平均值 在win7系统下MASM6.0下成功运行
汇编程序 求数组元素的最大值和最小值汇编程序 求数组元素的最大值和最小值汇编程序 求数组元素的最大值和最小值
c语言利用指针求数组的最大值与最小值,下载资源,数组可扩展。
编写自定义函数max,用来求三个数的最大值(要求:数据的输入、输出在主函数中实现)。
C#数组中五个数的最大值.cs
LABVIEW是NI公司开发的软件,其实用性很高,这里给出的是:在前面板中输入3个数,要求输出三个数的最大值
本程序能根据用户的要求,由用户决定比较的数字的总数,并由用户输入要比较的数字,然后打印出最大值
本题要求编写程序,找出给定的n个数中的最大值及其对应的最小下标(下标从0开始)。 输入格式: 输入在第一行中给出一个正整数n(1≤10)。第二行输入n个整数,用空格分开。 输出格式: 在一行中输出最大值及最大值...
Labview 编写的代码,求数组最大值与最小值
本程序能根据用户的需要,通过数组求任意多个数字的最大值
求3个数的最大值 求3个数的最大值 求3个数的最大值 求3个数的最大值