풍구 의 돼지 - 중국 우 시장

3356 단어
바람구멍 아래 서 는 돼지 도 날 수 있다.현재 중국 주식시장 의 상승 장 세 는 정말 7 년 을 놓 쳤 다 고 말 할 수 있다.역 사 를 돌 이 켜 볼 기 회 를 드 리 겠 습 니 다. 한 주식 이 n 일 연속 가격 추 세 를 알 고 있 습 니 다. 길이 가 n 인 정수 배열 에 따 르 면 배열 의 i 번 째 요소 (prices [i] 는 이 주식 의 i 일 째 주 가 를 대표 합 니 다.만약 당신 이 처음에 주식 이 없 었 다 고 가정 하지만, 기껏해야 두 번 이나 1 주 를 사서 1 주 를 팔 기회 가 있 었 고, 매입 하기 전에 반드시 수중 에 주식 이 없다 는 것 을 보증 해 야 한다.두 번 의 거래 기 회 를 모두 포기 하면 수익 은 0 이다.알고리즘 을 설계 하여 당신 이 얻 을 수 있 는 최대 수익 을 계산 하 세 요.입력 수치 범위: 2 < = n < = 100, 0 < = prices [i] < = 100
public class Solution {

    public final static int MAXN=105; 

    /** *             * * @param prices Prices[i]  i     * @return    */
    public int calculateMax(int[] prices) {
        if(prices==null || prices.length<2){
            return 0;
        }

        //left[i]  0 i          
        //minx      
        int left[]=new int[MAXN];
        left[0]=0;
        int minx=prices[0];
        for(int i=1;i<prices.length;i++){
            left[i]=Math.max(left[i-1],prices[i]-minx);
            minx=Math.min(minx, prices[i]);
        }

        //right[i]  i len-1          
        //minx      
        int right[]=new int[MAXN];
        right[prices.length-1]=0;
        int maxx=prices[prices.length-1];
        for(int i=prices.length-2;i>=0;i--){
            right[i]=Math.max(right[i+1],maxx-prices[i]);
            maxx=Math.max(maxx, prices[i]);
        }

        int ans=0;
        for(int i=0;i<prices.length;i++){
            ans=Math.max(ans,left[i]+right[i]);
        }
        return ans;
    }
}

좋은 웹페이지 즐겨찾기