LintCode 1691 · Best Time to Buy and Sell Stock V.java

	// Appproach #1 - T O(n log n).
	public class Solution {
	/**
	* @param A: the array A
	* @return: return the maximum profit
	*/
	public int getAns(int[] A) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int profit = 0;
	Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1 - o2);
	for (int a : A) {
	if (!pq.isEmpty() && pq.peek() < a) {
	// greedy: found business proposition
	profit += a - pq.poll();
	// correctness: in case you will find even better business proposition
	pq.offer(a);
	}
	pq.offer(a);
	}
	return profit;
	}
	}

view raw LintCode 1691 · Best Time to Buy and Sell Stock V.java hosted with ❤ by GitHub