kryzoo.m
BAN USERobject MaxWindowSum {
def getMax(numbers: Seq[Int], k: Int): Seq[Seq[Int]] = {
val sums = (0 to (numbers.size - k)).map(i => (i, (i to (i+k-1)).map(numbers(_)).sum)).toList
val sortedSums = sums.sortBy(_._2).reverse
val solution = getMaxInternal(sortedSums, k, 3)
getSolutionWindows(solution, numbers, k)
}
private def checkSolution(solution: Seq[(Int, Int)], n: Int): Seq[(Int, Int)] = if (solution.size == n) solution else Seq()
private def getMaxInternal(idxAndNumber: Seq[(Int,Int)], k: Int, n: Int): Seq[(Int, Int)] = {
val theBest = idxAndNumber.lift(0)
if (theBest.isDefined && idxAndNumber.size >= n) {
if(n == 1) {
//if you are looking for one value only then just take the best
Seq(theBest.get)
} else {
val (rest, overlapped) = idxAndNumber.drop(1).partition(el => {
val dist = math.abs(theBest.get._1 - el._1)
dist >= k
})
val firstSolution = getMaxInternal(rest, k, n - 1) ++ theBest
val firstSolutionValue = calcValue(firstSolution)
if (!overlapped.isEmpty || firstSolution.size < n) {
//check solution for intersected windows
val alternativeSolution = getMaxInternal(idxAndNumber.drop(1), k, n)
val alternativeSolutionValue = calcValue(alternativeSolution)
if (firstSolutionValue >= alternativeSolutionValue)
checkSolution(firstSolution, n)
else {
checkSolution(alternativeSolution, n)
}
} else
checkSolution(firstSolution, n)
}
} else {
//just nothing more to select - no solution
Seq()
}
}
private def calcValue(solution: Seq[(Int,Int)]): Long = solution.map(_._2).sum
private def getSolutionWindows(solution: Seq[(Int, Int)], numbers: Seq[Int], k: Int): Seq[Seq[Int]] =
solution.sortBy(_._1).map(el => numbers.slice(el._1, el._1 + k))
def main(args: Array[String]) {
val solution = getMax(Seq(2,2,4,4,2,2,1,1,1,1,1,1,1,1,1,2,1,2,1,1,1), 3)
// val solution = getMax(Seq(1,2,1,2,6,7,5,1), 2)
println("solution: %s, value: %d".format(solution, solution.map(_.sum).sum))
}
}
Recursive approach in Scala
object CoverIntervals {
case class Interval(start: Int, end: Int)
def findOneCoveringInterval(intervals: Set[Interval], target: Interval): Boolean =
intervals.exists(interval => interval.start <= target.start && interval.end >= target.end)
def partlyCovers(el: Interval, target: Interval): Boolean =
(el.start < target.start && el.end >= target.start) || (el.start < target.end && el.end >= target.end)
def cutTarget(interval: Interval, target: Interval): Interval =
if (interval.start < target.start && interval.end >= target.start)
Interval(interval.end, target.end)
else if (interval.start < target.end && interval.end >= target.end)
Interval(target.start, interval.start)
else throw new RuntimeException("unexpected arg: " + interval + " " + target)
def findMinInterval(intervals :Set[Interval], target: Interval): Option[Int] = {
if (findOneCoveringInterval(intervals, target))
Some(1)
else {
val partlyCovered = intervals.filter(el => partlyCovers(el, target))
if (partlyCovered.size == 0)
Option.empty
else {
val res = for {
interval <- partlyCovered
number <- findMinInterval(intervals - interval, cutTarget(interval, target))
} yield (number)
if (res.isEmpty)
Option.empty
else
Option(res.min + 1)
}
}
}
}
@challapallirahul I started with the same idea, but it is not enough,
the problem is if you have period with several little profits whereas buying once for the whole period gives better profit. Below tests that your algorithm do not pass:
assertEquals(5, Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,8,6}, 2));
assertEquals(7, Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8,9,8,9,10}, 2));
assertEquals(8, Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8,9,8,9,10,2,5}, 2));
The previous solution of @PPD fails with check with this:
assertEquals(15, Stock.getMaxProfit(new int[] {1,7,1,7,1,7,10}, 2));
I propose something more complex but seems to work:
public class Stock {
static class TransactionPair {
public TransactionPair(int buyIdx, int sellIdx) {
this.buyIdx = buyIdx;
this.sellIdx = sellIdx;
}
int buyIdx;
int sellIdx;
}
public static int maxProfit(int[] prices, int fee) {
List<TransactionPair> transactionPairs = smallTransactions(prices, fee);
List<TransactionPair> mergedTransactions = mergeTransactionsLoop(transactionPairs, prices, fee);
int profit = calcProfit(mergedTransactions, prices, fee);
System.out.println("profit = " + profit);
System.out.println();
return profit;
}
private static List<TransactionPair> mergeTransactionsLoop(List<TransactionPair> transactionPairs, int[] prices, int fee) {
int pairNo;
List<TransactionPair> trMergerd = null;
List<TransactionPair> trBeforeMerge = transactionPairs;
do {
pairNo = trBeforeMerge.size();
System.out.println("profit before merge= " + calcProfit(trBeforeMerge, prices, fee));
trMergerd = mergeTransactions(trBeforeMerge, prices, fee);
trBeforeMerge = trMergerd;
} while (pairNo > trMergerd.size());
return trMergerd;
}
private static List<TransactionPair> mergeTransactions(List<TransactionPair> transactionPairs, int[] prices, int fee) {
List<TransactionPair> mergedTransactions = new ArrayList<>();
for (int i = 0; i < transactionPairs.size(); i++) {
if (i < (transactionPairs.size() - 1)) {
TransactionPair merged = new TransactionPair(transactionPairs.get(i).buyIdx, transactionPairs.get(i + 1).sellIdx);
if (calcTrasactionProfit(prices, fee, transactionPairs.get(i)) + calcTrasactionProfit(prices, fee, transactionPairs.get(i + 1))
< calcTrasactionProfit(prices, fee, merged)) {
mergedTransactions.add(merged);
i++;
} else {
mergedTransactions.add(transactionPairs.get(i));
}
} else {
mergedTransactions.add(transactionPairs.get(i));
}
}
return mergedTransactions;
}
private static int calcProfit(List<TransactionPair> transactionPairs, int[] prices, int fee) {
return transactionPairs.stream().mapToInt(tr -> calcTrasactionProfit(prices, fee, tr)).sum();
}
private static int calcTrasactionProfit(int[] prices, int fee, TransactionPair tr) {
return prices[tr.sellIdx] - prices[tr.buyIdx] - fee;
}
private static List<TransactionPair> smallTransactions(int[] prices, int fee) {
List<TransactionPair> transactionPairs = new ArrayList<>();
int lastProfit = 0;
int lastLocalMinValue = Integer.MAX_VALUE;
int lastLocalMinIx = -1;
int lastLocalMaxValue = Integer.MIN_VALUE;
int lastLocalMaxIx = -1;
boolean lookToBuy = true;
for (int i = 0; i < prices.length; i++) {
System.out.println(String.format("prices(%d)=%d, %b", i, prices[i], lookToBuy));
if (lookToBuy) {
lastProfit = 0;
if (prices[i] <= lastLocalMinValue) {
lastLocalMinValue = prices[i];
lastLocalMinIx = i;
} else {
lookToBuy = false;
System.out.println("buy point at " + lastLocalMinIx + " for " + lastLocalMinValue);
}
}
if (!lookToBuy) {
if (prices[i] >= lastLocalMaxValue) {
lastLocalMaxValue = prices[i];
lastLocalMaxIx = i;
} else {
int diff = lastLocalMaxValue - lastLocalMinValue;
if (diff > fee && (diff - fee) > lastProfit) {
lastProfit = diff - fee;
System.out.println("sell point at " + lastLocalMaxIx + " for " + lastLocalMaxValue + " profit is " + lastProfit);
lookToBuy = true;
transactionPairs.add(new TransactionPair(lastLocalMinIx, lastLocalMaxIx));
lastLocalMinValue = prices[i];
lastLocalMinIx = i;
lastLocalMaxValue = Integer.MIN_VALUE;
}
}
}
}
if (!lookToBuy) {
int diff = prices[prices.length - 1] - lastLocalMinValue;
if (diff > fee && (diff - fee) > 0) {
lastProfit = diff - fee;
System.out.println("sell point at the end, profit " + lastProfit);
transactionPairs.add(new TransactionPair(lastLocalMinIx, prices.length - 1));
}
}
return transactionPairs;
}
public static void main(String[] args) {
assert(3 == Stock.maxProfit(new int[] {3,3,2,6}, 1));
assert(3 == Stock.maxProfit(new int[] {3,3,2,6,5,5}, 1));
assert(0 == Stock.maxProfit(new int[] {9,8,7,6,5,4}, 1));
assert(0 == Stock.maxProfit(new int[] {1,1,1,1,1,1}, 1));
assert(2 == Stock.maxProfit(new int[] {1,1,3,4,3,1}, 1));
assert(4 == Stock.maxProfit(new int[] {1,2,3,4,5,6}, 1));
assert(3 == Stock.maxProfit(new int[] {1,2,3,4,3,1,2,3,1}, 1));
assert(7 == Stock.maxProfit(new int[] {1,10,8,2}, 2));
assert(8 == Stock.maxProfit(new int[] {1,10,2,5}, 2));
assert(5 == Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,8,6}, 2));
assert(7 == Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8,9,8,9,10}, 2));
assert(8 == Stock.maxProfit(new int[] {2,2,1,2,3,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,7,8,9,8,9,10,2,5}, 2));
assert(15 == Stock.maxProfit(new int[] {1,7,1,7,1,7,10}, 2));
}
}
- kryzoo.m March 22, 2017