TopCoder Problem Statement - MostProfitable
Determine the most profitable item sold based on cost, price, and the number of sales.
01: /* 02: TopCoder 03: Single Round Match: 153 04: Division: 2 05: Level: 1 06: Points: 250 07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1774 08: */ 09: 10: public class MostProfitable { 11: 12: public String bestItem(int[] costs, int[] prices, int[] sales, 13: String[] items) { 14: 15: int maxProfitIdx = -1; 16: int maxProfitAmt = Integer.MIN_VALUE; 17: 18: /* 19: * For each item, calculate the profit. If it's greater than any 20: * we've seen so far, store that amount and its index. 21: * The profit is calculated as the (price - cost) times the number of 22: * sales. 23: */ 24: for (int i = 0; i < costs.length; i++) { 25: int profit = (prices[i] - costs[i]) * sales[i]; 26: if (profit > maxProfitAmt) { 27: maxProfitIdx = i; 28: maxProfitAmt = profit; 29: } 30: } 31: 32: /* 33: * If the profit on our most profitable item is greater than 0, 34: * return it's name. If there are no profitable items, 35: * return an empty string. 36: */ 37: if (maxProfitAmt > 0) { 38: return items[maxProfitIdx]; 39: } else { 40: return ""; 41: } 42: } 43: }
There's just two steps to solving this problem. First, we need to loop through each item and calculate it's profit. This is given by the equation on line 25: profit = (prices[i] - costs[i]) * sales[i];
Then, for each profit, we need to determine if it's greater than any previously seen value; and if so, we store both the index of that item as well as the profit. This is done on lines 26-29. By requiring the new profit to be greater than maxProfitAmt (as opposed to greater than or equal to), we ensure that in cases of a tie, the first value remains.
No comments:
Post a Comment