学步园

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Title: Longest_Up.java
 * @Package
 * @Description: TODO
 * @author nutc
 * @date 2013-9-8 下午7:16:34
 * @version V1.0
 */
public class Longest_Up {

	public static void main(String args[]) {

		
		Longest_Up l = new Longest_Up();
		int[] a = {1,1};
		System.out.println(l.largestRectangleArea1(a));
	}
	
	
	public int largestRectangleArea1(int[] height) {
        if(height==null||height.length==0) return 0;
        if(height.length==1) return height[0];
        
        int[] dp = new int[height.length];
        int[] rdp = new int[height.length];
        findDp(height,dp);
        findRdp(height,rdp);
        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(rdp));
        int max = 0;
        for(int i=0;i<height.length;i++){
        	int area = (rdp[i]-1-(dp[i]+1)+1) * height[i];
        	if(area>max)
        		max = area;
        }
        return max;
    }
	
	public void findDp(int[] a,int[] dp){
		Arrays.fill(dp, -1);
		for(int i=1;i<a.length;i++){
			int j= i-1;
			while(j>=0 && a[j]>=a[i]) //这里有等号！！
				j = dp[j];
			dp[i]=j;
		}
	}
	
	public void findRdp(int[] a,int[] dp){
		Arrays.fill(dp, a.length);
		for(int i=a.length-2;i>=0;i--){
			int j= i+1;
			while(j<a.length && a[j]>=a[i])  //这里有等号！！
				j = dp[j];
			dp[i]=j;
		}
	}
	



}