学步园

已知一段时间内股价有涨跌，例如 {3,6,1,4,7,3,8,8,3,5}.求最大获利是多少。不能买空卖空。

例如，上例应该是第3天买，第7天卖获利最大，获利是7元。

我没有想出什么好办法，下例就是循环的比差值。但是实际上有O(n)的解法。

public class App {

	public static void main(String[] args) {

		int[] a={3,6,1,4,7,3,8,8,3,5};		
		int d=0;
		for(int i=1;i<a.length;i++){
			int[] x = Arrays.copyOfRange(a,0,i);
			int[] y = Arrays.copyOfRange(a,i,a.length);
			if(d < highest(y) - lowest(x) ){
				d = highest(y) - lowest(x);
			}
		}
		
		System.out.print(d);
	}
	
	public static int lowest(int[] x){
		int i=x[0];
		for(int j=0;j<x.length-1;j++){
			if(x[j] > x[j+1]){
				i = x[j+1];
			}
		}		
		return i;
	}
	
	public static int highest(int[] x){
		int i=x[0];
		for(int j=0;j<x.length-1;j++){
			if(x[j] < x[j+1]){
				i = x[j+1];
			}
		}		
		return i;
	}
}

下面是O(n)的解法：

public class App {

	public static void main(String[] args) {

		int[] a={ 4,1,3,6,6,7,8,9,2,11};
		int[] env={0,0};
		env[0] = a[0];
		env[1] = a[0];
		int maxD=0;
		
		for(int i=1; i<a.length;i++){
			if(a[i] > env[1]){
				env[1] = a[i];
				if(maxD < env[1] - env[0]){
					maxD = env[1] - env[0];
				}
			}else if(a[i] < env[0]){
				env[0] = a[i];
				env[1] = a[i];
			}
		}
		
		System.out.print(maxD);
	}
}

env[0] 代表low值，env[1]代表high值。用maxD记录最大差值，当low和high发生变化时更新一下maxD。