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;
        }
    }
}