O(N(N - K)) solution with Double Linked List.


  • 1
    C

    The trick is to find out all peaks/valley pairs. Make each pair a double linkedlist node.
    Using the following principles to shorten the length of the linkedlist to k:

    1. Find the minimum peak/valley difference node then remove it.
    2. Or combine continuous two nodes where the (second node's peak/valley difference + first node's peak/valley difference) - (second node's peak - first node's valley) is minimum.

    Do 1 or 2 depending on whose one is smaller. Traverse the linkedlist n - k times until the linkedlist is k.

    The n is actually not the number of transaction days but the number valley/peak pairs.

        class DLNode{
        DLNode next,prev;
        Point cur_v;
        public DLNode(){
            cur_v = new Point();
        }
    }
    public int maxProfit(int k, int[] prices) {
        DLNode head = null, tmp = null, curtmp = new DLNode();
        int cur_size = 0;
        int curstatus = -1;
        int res = 0;
        for(int i = 0; i < prices.length; i++){
                if(i != prices.length - 1 && prices[i] < prices[i + 1]){
                    if(curstatus == -1){
                        curtmp.cur_v.x = prices[i];
                    }
                    curstatus = 1;
                }else if(i == prices.length - 1 || prices[i] > prices[i + 1]){
                    if(curstatus == 1){
                        curtmp.cur_v.y = prices[i];
                        if(tmp == null){
                            head = curtmp;
                            tmp = curtmp;
                        }else{
                            tmp.next = curtmp;
                            curtmp.prev = tmp;
                            tmp = tmp.next;
                        }
                        res += curtmp.cur_v.y - curtmp.cur_v.x;
                        cur_size++;
                        curtmp = new DLNode();
                    }
                    curstatus = -1;
                }
        }
        while(cur_size > k){
            tmp = head;
            boolean isCombined = false;
            int mindiff = Integer.MAX_VALUE;
            DLNode candidate = null;
            while(tmp != null){
                int cur_diff = tmp.cur_v.y - tmp.cur_v.x;
                if(cur_diff < mindiff){
                    candidate = tmp;
                    mindiff = cur_diff;
                    isCombined = false;
                }
                if(tmp.next != null){
                    cur_diff = tmp.cur_v.y - tmp.next.cur_v.x;
                    if(cur_diff < mindiff){
                        mindiff = cur_diff;
                        candidate = tmp;
                        isCombined = true;
                    }
                }
                tmp = tmp.next;
            }
            if(isCombined){
                candidate.next.cur_v.x = candidate.cur_v.x;
            }
            if(head == candidate)head = candidate.next;
            if(candidate.next != null)candidate.next.prev = candidate.prev;
            if(candidate.prev != null)candidate.prev.next = candidate.next;
            cur_size--;
            res -= mindiff;
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.