Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/c5216eea68d50fa87014606fb4ea634a to your computer and use it in GitHub Desktop.
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
/*
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