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

• 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){
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){
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;
}