# A different way to solve with logic in O(n*k), non DP code Java

• ``````public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n < 2) {
return 0;
}
int count = 0;
int[] diff = new int[n-1];
// for the case where k is large enough to get all the profit trades
for (int i = 0; i < n-1; i++) {
diff[i] = prices[i+1] - prices[i];
if (diff[i] > 0) {
count++;
}
}
int res = 0;
// able to get all profit
if (count <= k) {
for (int i = 0; i < n-1; i++) {
res += Math.max(0, diff[i]);
}
return res;
}
// buy: -1, sell: 1, other: 0
int[] actions = new int[n];
int buy = 0, sell = 0;
//  the logic here is:
//  when you have a result from k = 1 and begin k = 2,
//  you will see you will always end up keeping your action made for buy and sell actions in k = 1;
//  consider: if you want to make two different trades and disregard the previous one,
//            you will always end up replace one of the trade's buy with the buy date in k=1 and the sell date in k=1
// when k is greater than 1, the same logic applies
for (int i = 1; i <= k; i++) {
int l = 0, r = 0;
boolean within = false;
while (r < n) {
if (!within) {// if you are out side the previous transaction period, look for max profit as normal
sell = r;
while (r < n && actions[r] != -1) {
}
r++;
}
within = !within;
} else {// if you are within the previous transaction period,
// you want to find a high price to sell first before you buy low to make a profit to meet the requirement
sell = r;
while (r < n && actions[r] != 1) {
sell = prices[r] < prices[sell] ? sell : r;
}
r++;
}
within = !within;
}
r++;
}