求数组的最大差值（maxij问题） 博客分类： 数据结构&算法

题目：

数组a[0..n-1]，找出i和j使得a[j] - a[i]的值最大。

注意j > i。

要求是时间复杂度O(n),空间复杂度O(1)。

思路：
  样例数组 11,1,5,8,11,2,3,2,11,5,3
  1.先从后到前依次求出相邻2个数的差值，得到 {-2,-6,9,-1,1,-9,3,3,4,-10}
  2.问题转化为求差值数组最大和序列，从前至后遍历该数组，保留所有的序列和为正数的和，得到{9,8,9,3,6,10}，求最大值为 10

代码：

    
	static int maxIj(int[] arr){
		for(int i=arr.length-1; i > 0;i--){
			arr[i] = arr[i] - arr[i-1];
		}
		arr[0] = 0 ;
		int n = 0;
		for(int i=1; i<arr.length;i++) {
			n = n + arr[i];
			if(n > 0 && n > arr[0]) {
				arr[0] = n;
			} else {
				n = 0;
			}
		}
		int maxIj = arr[0];
		System.out.println(CollectorUtil.toString(arr));
		return maxIj;
	}
	
	
	public static void main(String[] args) {
		int[] arr = new int[]{11,3,5,8,11,2,3,2,11,5,3};
		int max = maxIj(arr);
		System.out.println(max);
		
		System.out.println("---------------");
		
	}