题解 | #牛群买卖计划III#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfitIII (int[] prices) {
        int n = prices.length ; 
        int[] sum = new int[n] ; 
        for(int i = 0;i < n;i++){
            sum[i] = prices[i] ; 
            if(i > 0){
                sum[i] += sum[i-1] ; 
            }
        }
        int[] st = new int[n] ; 
        int top = 0; 
        int ans = 0; 
        for(int i = n-1;i >= 0;i--){
            if(top == 0 || prices[st[top-1]] < prices[i]){
                if(top > 0){
                    ans += prices[st[top-1]]*(st[top-1]-1-i) - (sum[st[top-1]-1] - sum[i]);
                }
                st[top++] = i ; 
            }
        }
        if(top > 0 && st[top-1] > 0){
            ans += prices[st[top-1]]*(st[top-1]) - (sum[st[top-1]-1]) ; 
        }
        return ans ; 
        // write code here
    }
}

从后往前单调栈O(n)