Created
February 13, 2018 21:48
-
-
Save jianminchen/c5216eea68d50fa87014606fb4ea634a to your computer and use it in GitHub Desktop.
Float numbers and operators - Julia performance on Jan. 25, 2018 - copy from the video clip, 55:01/1:00:16
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
/* | |
Given a list of float numbers, insert “+”, “-”, “*” or “/” between each consecutive | |
pair of numbers to find the maximum value you can get. For simplicity, assume that | |
all operators are of equal precedence order and evaluation happens from left to right. | |
Example: | |
(1, 12, 3) -> 1 + 12 * 3 = 39 | |
float getMaxNumber(float[] nums)... | |
Keyword: | |
a list of float number | |
four operator: +, -, *, / algebra | |
insert operator between each consecutive pair of numbers | |
1, 12, +, 2, 10, | |
1, 2, -, 3, 4 | |
1, 2, *, 3, 4 | |
1, 2, /, 3, 4 | |
Ask: | |
Find maximimum value -> greedy algorithm | |
you can get | |
Constraints: | |
equal precedence order - 1 + 2 * 3 = 1 + 6 = 7 | |
1 + 2 * 3 = 3 * 3 = 9 | |
evaluation order is from left to right | |
-> scan the float number from left to right | |
1, 12, 3 | |
1, 12, Operator? 3 | |
4 options | |
brute force and figure out which one is biggest one | |
float number is very long, 10 | |
1, 2, 3, 4,, 5, 6, 7, 8,9, 10 put five operator, | |
each operator has 4 options | |
4^5 -> NP complete | |
subprogramm | |
1, 2 + ? 1 + 2 = 2 + - / * subproblem undefined | |
- ? 1 -2 = -1 subproblem find smallest problem | |
* ? 1 * 2 = 2 subprobem | |
/? 1/ 2 = 0.5 | |
10:27 pm - 10:29 quiet time | |
1, 2, +, 3, 4 | |
= 1 + 2 =3 | |
3, 3, operator + 4 -> make any sense | |
x1, op1 x2, op2 ... op_{n-1} Xn (n-1 operators) | |
x1, op x2, op1, x3, op2, | |
Depth first search | |
+: x1 + x2 | |
-: x1 - x2 | |
*: x1 * x2 | |
/: x1/x2 | |
Base case: | |
1 -> return 1 | |
1, 2 -> return maximum | |
Math.Max(1+2, 1-2, 1*2, 1/2); | |
1, 2, 3 -> return maximum | |
forward | |
-> | |
reverse -> | |
1, 2, 3 | |
1, 2, 3, 4 | |
between each pair, must be an operators | |
1,12,-3 = 1-12 * -3 = 33 | |
1, 12, -3 => 1 -12 = -11 * -3 = 33 | |
[1, 2, -3] , 7, not produce 8, not product 9 | |
1 | |
13 12 -11 1/12 Mat | |
look at those four number, how do you figure out maximum value by looking at | |
those number themselves? Do this hint help? | |
*/ | |
class Solution | |
{ | |
static void Main(string[] args) | |
{ | |
for (var i = 0; i < 5; i++) | |
{ | |
Console.WriteLine("Hello, World"); | |
} | |
} | |
public static double getMaximumValue(double[] numbers, int start ) /// [1, 2, -3], 7 | |
{ | |
if(numbers == null || numbers.Length == 0 || start >= numbers.Length) // ok | |
{ | |
return 0; // ? | |
} | |
var length = numbers.Length; // 3 | |
var current = numbers[0]; // 1 | |
//base case | |
if(length == 0) | |
{ | |
return current; | |
} | |
// flat | |
var subProblem = getMaximumValue(numbers, start + 1); /// okk | |
var subProblemSubstrction = getMinimuValue(numbers, start + 1); | |
var addition = current + subProblem; | |
var subtarction = current - subProblemSubstrction; | |
var multiplication = current > 0? current * subProblem : current * subProblemSubstrction; | |
var division = current / subProblemSubstrction; | |
return Math.Max(addition, subtarction,multiplication, division ); | |
} | |
Time: 4^ n - 1 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment