Skip to content

Instantly share code, notes, and snippets.

@GarrettS
Last active April 10, 2019 16:18
Show Gist options
  • Save GarrettS/44fbad1e8dbe7cbb80a12155f2789a2c to your computer and use it in GitHub Desktop.
Save GarrettS/44fbad1e8dbe7cbb80a12155f2789a2c to your computer and use it in GitHub Desktop.
Max Range Sum — JP Morgan Chase Interview Question // source https://jsbin.com/cikekev
<!DOCTYPE html>
<html>
<head>
<meta name="description" content="JP Morgan Chase Intervew Question">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JP Morgan Chase Intervew Question</title>
</head>
<body>
<script id="jsbin-javascript">
/**
* Max Range Sum
Difficulty: Easy
Time Limit: 30 min
Description
Bob is developing a new strategy to get rich in the stock market. He wishes to invest his portfolio
for 1 or more days, then sell it at the right time to maximize his earnings. Bob has painstakingly
tracked how much his portfolio would have gained or lost for each of the last N days. Now he
has hired you to figure out what would have been the largest total gain his portfolio could have
achieved.
Example: Bob kept track of the last 10 days in the stock market. On each day, the gains/losses
are as follows: 7 -3 -10 4 2 8 -2 4 -5 -2. If Bob entered the stock market on day 4 and exited on
day 8, his gains would have been 16 (4 + 2 + 8 + -2 + 4).
Input
The input consists of integers on a line separated by spaces. The input contains N, the number of
days (0 &lt; N &lt; 10000), followed by N integers D (-10000 &lt; D &lt; 10000) indicating the gain or loss
on that day.
Output
For each test case, print a line containing the maximum possible gain over the period. If no gain
is possible, print 0.
Test 1
Input
10 7 -3 -10 4 2 8 -2 4 -5 -6
Expected Output
16
*/
function getBestRunProfit(inputString) {
let days = getDaysNumberArray(inputString);
return maxSubArraySum(days);
function maxSubArraySum(days) {
let maxSoFar = 0,
currentTotal = 0;
for (let i = 0; i < days.length; i++) {
currentTotal = currentTotal + days[i];
if (maxSoFar < currentTotal) {
maxSoFar = currentTotal;
}
if (currentTotal < 0) {
currentTotal = 0;
}
}
return maxSoFar;
}
function getDaysNumberArray(inputString) {
return inputString.trim().split(" ").map(day => +day);
}
}
console.log(getBestRunProfit("1 2 3 -5 1 2 3 -5 1"));
console.log(getBestRunProfit("1 2 3 -6 1 2 4"));
console.log(getBestRunProfit("1 2 3"));
console.log(getBestRunProfit("10 7 -3 -10 4 2 8 -2 4 -5 -6"));
</script>
<script id="jsbin-source-javascript" type="text/javascript">/**
* Max Range Sum
Difficulty: Easy
Time Limit: 30 min
Description
Bob is developing a new strategy to get rich in the stock market. He wishes to invest his portfolio
for 1 or more days, then sell it at the right time to maximize his earnings. Bob has painstakingly
tracked how much his portfolio would have gained or lost for each of the last N days. Now he
has hired you to figure out what would have been the largest total gain his portfolio could have
achieved.
Example: Bob kept track of the last 10 days in the stock market. On each day, the gains/losses
are as follows: 7 -3 -10 4 2 8 -2 4 -5 -2. If Bob entered the stock market on day 4 and exited on
day 8, his gains would have been 16 (4 + 2 + 8 + -2 + 4).
Input
The input consists of integers on a line separated by spaces. The input contains N, the number of
days (0 &lt; N &lt; 10000), followed by N integers D (-10000 &lt; D &lt; 10000) indicating the gain or loss
on that day.
Output
For each test case, print a line containing the maximum possible gain over the period. If no gain
is possible, print 0.
Test 1
Input
10 7 -3 -10 4 2 8 -2 4 -5 -6
Expected Output
16
*/
function getBestRunProfit(inputString) {
let days = getDaysNumberArray(inputString);
return maxSubArraySum(days);
function maxSubArraySum(days) {
let maxSoFar = 0,
currentTotal = 0;
for (let i = 0; i < days.length; i++) {
currentTotal = currentTotal + days[i];
if (maxSoFar < currentTotal) {
maxSoFar = currentTotal;
}
if (currentTotal < 0) {
currentTotal = 0;
}
}
return maxSoFar;
}
function getDaysNumberArray(inputString) {
return inputString.trim().split(" ").map(day => +day);
}
}
console.log(getBestRunProfit("1 2 3 -5 1 2 3 -5 1"));
console.log(getBestRunProfit("1 2 3 -6 1 2 4"));
console.log(getBestRunProfit("1 2 3"));
console.log(getBestRunProfit("10 7 -3 -10 4 2 8 -2 4 -5 -6"));</script></body>
</html>
/**
* Max Range Sum
Difficulty: Easy
Time Limit: 30 min
Description
Bob is developing a new strategy to get rich in the stock market. He wishes to invest his portfolio
for 1 or more days, then sell it at the right time to maximize his earnings. Bob has painstakingly
tracked how much his portfolio would have gained or lost for each of the last N days. Now he
has hired you to figure out what would have been the largest total gain his portfolio could have
achieved.
Example: Bob kept track of the last 10 days in the stock market. On each day, the gains/losses
are as follows: 7 -3 -10 4 2 8 -2 4 -5 -2. If Bob entered the stock market on day 4 and exited on
day 8, his gains would have been 16 (4 + 2 + 8 + -2 + 4).
Input
The input consists of integers on a line separated by spaces. The input contains N, the number of
days (0 &lt; N &lt; 10000), followed by N integers D (-10000 &lt; D &lt; 10000) indicating the gain or loss
on that day.
Output
For each test case, print a line containing the maximum possible gain over the period. If no gain
is possible, print 0.
Test 1
Input
10 7 -3 -10 4 2 8 -2 4 -5 -6
Expected Output
16
*/
function getBestRunProfit(inputString) {
let days = getDaysNumberArray(inputString);
return maxSubArraySum(days);
function maxSubArraySum(days) {
let maxSoFar = 0,
currentTotal = 0;
for (let i = 0; i < days.length; i++) {
currentTotal = currentTotal + days[i];
if (maxSoFar < currentTotal) {
maxSoFar = currentTotal;
}
if (currentTotal < 0) {
currentTotal = 0;
}
}
return maxSoFar;
}
function getDaysNumberArray(inputString) {
return inputString.trim().split(" ").map(day => +day);
}
}
console.log(getBestRunProfit("1 2 3 -5 1 2 3 -5 1"));
console.log(getBestRunProfit("1 2 3 -6 1 2 4"));
console.log(getBestRunProfit("1 2 3"));
console.log(getBestRunProfit("10 7 -3 -10 4 2 8 -2 4 -5 -6"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment