首页 > 代码库 > 动态规划经典问题03：数组中最大的数对差（或最小的数对差）

动态规划经典问题03：数组中最大的数对差（或最小的数对差）

2024-07-21 12:25:35   224人阅读

题目：在数组中，数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16减去5的结果。

参考：http://zhedahht.blog.163.com/blog/static/2541117420116135376632/

讨论区：http://stackoverflow.com/questions/11858790/find-the-largest-possible-difference-in-an-array-with-the-smaller-integer-occuri

【分析】自顶向下分析，diff[i]记录0~i的最大数对之差，max[i]记录0~i的最大数，则状态递归方程为：

diff[i+1]=Math.max(max[i]-array[i+1]，diff[i] )

  自底向上分析， 初试max[1]=2，diff[1]=2-4=-2。max[2]=4，diff[2]=Max(4-1，diff[1])=3。max[3]=4，diff[3]=Max(4-16，diff[2])=3。……

  算法复杂度为O(n)。

/** 
 * 创建时间：2014年9月5日 下午5:27:46 
 * 项目名称：Test 
 * @author Cao Yanfeng 
 * @since JDK 1.6.0_21 
 * 类说明：  动态规划解数组中的最大数对差
 */
public class MaxDiffofArray {
 
         /**
          * @paramargs
          */
         public static void main(String[] args) {
                   // TODO Auto-generated method stub
                   int[] array={1,15,2,5,0,-1};
                   System.out.println(getMaxDiff(array));
 
         }
         public static int getMaxDiff(int[] array) {
                   int length=array.length;
                   if (length==1) {
                            return-999;
                   }
                   if (length==2) {
                            return array[2]-array[1];
                   }
                   int max=array[0];
                   int maxDiff=max-array[1];
                   for (int i = 2; i < length; i++) {
                            if (array[1]>max) {
                                     max=array[i-1];
                            }
                            int currentDif=max-array[i];
                            if (currentDif>maxDiff) {
                                     maxDiff=currentDif;
                            }
                   }
                   return maxDiff;
         }
}


动态规划经典问题03：数组中最大的数对差（或最小的数对差）


联系
我们