Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 29, 2018 19:04
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/f3b294cdc3b6e7345e27f1bc602b564e to your computer and use it in GitHub Desktop.
Save jianminchen/f3b294cdc3b6e7345e27f1bc602b564e to your computer and use it in GitHub Desktop.
Float numbers and operators - try to put n - 1 operators to get maximum value, n is the float number's length
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FindMaximumNumber
{
/*
Keyword:
a list of float number
four operator: +, -, *, / algebra
insert operator between each consecutive pair of numbers
Ask:
Find maximimum value -> greedy algorithm
Constraints:
equal precedence order - 1 + 2 * 3 = 1 + 6 = 7 - No
1 + 2 * 3 = 3 * 3 = 9 - Yes
evaluation order is from left to right
-> scan the float number from left to right
1, 12, -3, maximum number is 1 - 12 * (-3) = 33
1
/ / \ \
-11 13 1/12 12 -> Maximum and Minimum
*/
class Program
{
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase1()
{
var result = GetMaxNumber(new double[] { 1, 12});
}
public static void RunTestcase()
{
var input = new double[] { 1, 12, -3 };
var result = GetMaxNumber(input);
Debug.Assert(result[0] == 33);
}
public static double[] GetMaxNumber(double[] numbers)
{
if (numbers == null || numbers.Length == 0)
{
return new double[] { };
}
return GetMaxNumberHelper(numbers, 1, new double[] { numbers[0], numbers[0] });
}
/// <summary>
/// code review 1/29/2018
/// </summary>
/// <param name="numbers"></param>
/// <param name="startIndex"></param>
/// <param name="original"></param>
/// <returns></returns>
public static double[] GetMaxNumberHelper(double[] numbers, int startIndex, double[] original)
{
if (startIndex >= numbers.Length)
{
return original;
}
var length = numbers.Length;
var visit = numbers[startIndex];
var fourOperations = getFourOperations(original, visit);
var current = new double[] { fourOperations.Max(), fourOperations.Min() };
return GetMaxNumberHelper(numbers, startIndex + 1, current);
}
/// <summary>
/// code review 1/29/2018
/// </summary>
/// <param name="maxMin"></param>
/// <param name="number2"></param>
/// <returns></returns>
private static double[] getFourOperations(double[] maxMin, double number2)
{
var addition = maxMin[0] + number2;
var addition2 = maxMin[1] + number2;
var subtraction = maxMin[0] - number2;
var subtraction2 = maxMin[1] - number2;
var multiplication = maxMin[0] * number2;
var multiplication2 = maxMin[1] * number2;
var division = maxMin[0] / number2;
var division2 = maxMin[1] / number2;
return new double[] { addition, addition2, subtraction, subtraction2, multiplication, multiplication2, division, division2 };
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment