Created
February 6, 2018 22:21
-
-
Save jianminchen/dc6b840cd325dc75e2703547bbed3720 to your computer and use it in GitHub Desktop.
float numbers and operators - brute force solution - continuously play and then understand the algorithm.
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
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace floatNumberAndOperators | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var maximum = EvaluateMaximize(new double[] { 1, 12, -3 }); | |
} | |
/// <summary> | |
/// Float numbers and operators: +, -, *, / | |
/// What is the maximum number? | |
/// code review Feb. 6, 2018 | |
/// [1, 12, -3], 33, first two numbers 1 - 12 = -11 | |
/// This function is a brute force solution. | |
/// [1, 12, -3] brute force solution, there are 16 numbers and the maximum of 16 numbers should be 33. | |
/// The idea to prune the algorithm is to save only 2 numbers for next round. So each round | |
/// there are only possible 8 results, maximum and minimum values are calculated. So the total | |
/// time complexity will be (2 * 4) * n = O(n) algorithm. | |
/// </summary> | |
/// <param name="terms"></param> | |
/// <returns></returns> | |
public static double EvaluateMaximize(double[] terms) | |
{ | |
int N = terms.Length; | |
if (N > 16) | |
{ | |
throw new ArgumentException("Too complex for this solution"); | |
} | |
var intermediate = new double[1 << (2 * N)]; | |
int iInterm = 0; | |
double maximized = 0; | |
intermediate[iInterm++] = terms[0]; // 1 | |
/// 1 4 4^2 in total: (4^3 - 1)/ 4 - 1 | |
/// iMaxInterm 0 4 - 1 4^2 - 1 | |
for (int index = 1; index < N; index++) | |
{ | |
int iMaxInterm = iInterm - 1; | |
double m = 0; | |
for (int iPrev = iMaxInterm; iPrev >= 0; iPrev--) | |
{ | |
double prev = intermediate[iPrev]; | |
var startIndex = iPrev * 4; | |
var current = terms[index]; | |
intermediate[startIndex + 0] = prev * current; | |
intermediate[startIndex + 1] = prev / current; | |
intermediate[startIndex + 2] = prev - current; | |
intermediate[startIndex + 3] = prev + current; | |
if (index != N - 1) // skip if not the last term | |
continue; | |
m = Math.Max(m, intermediate[startIndex + 3]); | |
m = Math.Max(m, intermediate[startIndex + 2]); | |
m = Math.Max(m, intermediate[startIndex + 1]); | |
m = Math.Max(m, intermediate[startIndex + 0]); | |
} | |
maximized = m; | |
iInterm *= 4; | |
} | |
return maximized; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment