Last active
February 29, 2016 08:09
-
-
Save h2rashee/f7c3cbe3ffccdbd0e5d2 to your computer and use it in GitHub Desktop.
Given a set of stock prices modelled over time, determine the best gain from buying and selling the stock.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.*; | |
class StockAnalysis { | |
public static void main(String[] args) { | |
Scanner sc = new Scanner(System.in); | |
int n = sc.nextInt(); | |
int[] nums = new int[n]; | |
for(int i = 0; i < n; i++) { | |
nums[i] = sc.nextInt(); | |
} | |
System.out.println(findBiggestGain(nums)); | |
} | |
public static int findBiggestGain(int[] prices) { | |
return findBiggestGain(prices, 0); | |
} | |
public static int findBiggestGain(int[] prices, int i) { | |
int curMin = prices[i]; | |
int curMax = prices[i]; | |
i++; | |
for(; i < prices.length; i++) { | |
if(prices[i] > curMax) { | |
curMax = prices[i]; | |
} | |
if(prices[i] < curMin) { | |
// Look-ahead guarding | |
if(i+1 < prices.length) { | |
int diff = findBiggestGain(prices, i); | |
// Something ahead of us is better | |
if(diff > (curMax - curMin)) { | |
return diff; | |
} | |
} | |
// What we have is better | |
return curMax - curMin; | |
} | |
} | |
// Ended on a bland note? What we have measured is good then. | |
return curMax - curMin; | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment