【C# 每日一题7】求最大的结果,该怎么处理

【C# 每日一题7】求最大的结果

C# code

DescriptionGive you a expression,you can add some parenthesis to maximize result.Example as following:1 + 2 * 3Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3,then the result is 9,and so it is the maximization of the example.You job is to find the maximizaton of a expression. To simplify this problem,you can assume that expression contains only operator + and *,but note that integers may be negative.InputInput contains multiple test cases.Each case begin with a integer N(2&lt;=N&lt;=100), the number of integers of a expression.Then follows the expression.Integers and operator spearate with a single whitespace.OutputFor each case print a single line with the maximized value of the expression.Sample Input41 + 2 * 3 + -1Sample Output8

解释一下，输入一个数n代表有下面算式里面有n个数字，每个数字中间有一个符号（+ or * ）
之后输入这个算式
在随意加括号之后求出算式可以得到的最大值！
如：
4
1 + 2 * 3 + -1
变为( 1 + 2 ) * 3 + -1 = 8
输出最大的值！！

求实现！哈哈！

[解决办法]
类似24点？
[解决办法]
如果没有负数，把所有加号都括起来就最大了吧
[解决办法]
哦，n^3的DP可以，再想想有没有更好的方法。
[解决办法]
这个需要看有多少个负数~有多少个纯小数~来决定是用+还是*
[解决办法]
1 + 2 * 3 -1
括号所在位置，得到的值
0,2 =8
0,3 =6
1,3 =6
1,4 =6
2,4 =5
如果只能有1对括号，貌似循环是最直接的办法，尽管效率很不好。
[解决办法]
1 + 2 * 3 -1
括号所在位置，得到的值
0,2 =8
0,3 =6
1,3 =6
1,4 =6
2,4 =5

[解决办法]
碰到乘号就加括号吧，如果负数在最后就不管，负数在中间的情况考虑不出来，等待牛人....
[解决办法]
下面用动态规划，空间复杂度为O(N^2)，时间复杂度为O(N^3)：

C# code

void Test{    int i = Maximize("1 + 2 * 3 + -1"); //i=8}class Node{    public int Value {get; set;}    public char Operator {get; set;}    public static Node operator &(Node n1, Node n2)    {        int result = 0;        switch(n1.Operator)        {            case '+': result = n1.Value + n2.Value; break;            case '*': result = n1.Value * n2.Value; break;        }        return new Node() { Value = result, Operator = n2.Operator };    }}int Maximize(string expression){    List&lt;Node&gt; nodes = new List&lt;Node&gt;();    int lastValue = 0;    foreach (string s in expression.Split(' '))    {        if ("+-/*".Contains(s))        {            nodes.Add(new Node() { Value = lastValue, Operator = s[0]});        }        else        {            lastValue = int.Parse(s, System.Globalization.CultureInfo.InvariantCulture);        }    }    nodes.Add(new Node() { Value = lastValue, Operator = '+' });    Node[,] matrix = new Node[nodes.Count, nodes.Count];    for (int e = 0; e &lt; matrix.GetLength(0); e++)    {        matrix[e, e] = nodes[e];        for (int s = e - 1; s &gt;= 0; s--)        {            Node max = new Node(){Value = int.MinValue};            for (int split = e - 1; split &gt;= s; split--)            {                Node node = matrix[s, split] & matrix[split + 1, e];                if (node.Value &gt; max.Value) max = node;            }            matrix[s, e] = max;        }    }    return matrix[0, matrix.GetLength(0)-1].Value;}
------解决方案--------------------  
1 + 2 * 3 + -1
表达式本质上就是一颗树行结构，根节点是操作符，这个表达式实际上是树

         +
     1       -
  
           *     1
         2   3

的中序遍历，

这个问题的实质就是给你这种表达式树的后续遍历结果，在所有形成这种后续遍历的树结构中，找出和最大的那个
[解决办法]
NP复杂？？？？
[解决办法]
探讨

下面用动态规划，空间复杂度为O(N^2)，时间复杂度为O(N^3)：
C# code
void Test
{
    int i = Maximize("1 + 2 * 3 + -1"); //i=8
}

class Node
{
    public int Value {get; set;}
    public char Operator {get; set;}
    public……

[解决办法]
sorry，后面的说明没看清“ that expression contains only operator + and *”
不过，我有个问题：
-2 * -1 + 4
能否变成-2 * -(1 + 4) = 10
[解决办法]
探讨
...
try this expression
1 + 2 * 3 - 1 + 2 - 3
(1+2)*3-1+2-3 = 9, ls的答案貌似只有1

[解决办法]
粗略看了一下gomoku同志的代码，似乎没有考虑两边为负数*之后更大的情况，不知道说对了没有，没说对的话，gomoku不要介意呦。
[解决办法]
那个DP的解法不对吧，
如果是两个负数相乘的结果也可以是很大的不满足(max left)*(max right)
如果全为正数才能这么做！！！
[解决办法]
还是可以dp，只要把最小值也存下来就可以了。

探讨

那个DP的解法不对吧，
如果是两个负数相乘的结果也可以是很大的不满足(max left)*(max right)
如果全为正数才能这么做！！！

[解决办法]
探讨
粗略看了一下gomoku同志的代码，似乎没有考虑两边为负数*之后更大的情况，不知道说对了没有，没说对的话，gomoku不要介意呦。

[解决办法]
依我看来对于任意一个表达式a1?a2?a3?.....?an,其中?为'+'|'*',an为整数，我们只要对该表达式加上所有可能出现的括号再压栈运算取最大值即可。
对于上述表达式有(n-2)(n-1)/2种加括号的情况，设输入字符串为s,那么只要找出可以加‘(’的下标集合b1,和加')'的下标集合b2,易得b1=b2=n-1（对自己加括号是毫无意义的）,那么加括号的方法总数就是n-1+n-2+...+1=(n-1)(n-2)/2,而且这种方法用循环很容易实现。
后面就是根据上述方法产生的(n-2)(n-1)/2个新的字符串，也就是新的表达式压栈进行计算，最后求出最大值即可。这里负数可当做一般的数处理，不用再多做考虑了。
[解决办法]
肯定可以DP，总共有如下8种情况，

最大 + 最大 最大 + 最小 最小 + 最大 最小 + 最小
换成*还有4种，取8种中的最大和最小进行记录就可以了。

探讨

引用:

依我看来对于任意一个表达式a1?a2?a3?.....?an,其中?为'+'|'*',an为整数，我们只要对该表达式加上所有可能出现的括号再压栈运算取最大值即可。
对于上述表达式有(n-2)(n-1)/2种加括号的情况，设输入字符串为s,那么只要找出可以加‘(’的下标集合b1,和加')'的下标集合b2,易得b1=b2=n-1（对自己……

[解决办法]
探讨
依我看来对于任意一个表达式a1?a2?a3?.....?an,其中?为'+'|'*',an为整数，我们只要对该表达式加上所有可能出现的括号再压栈运算取最大值即可。
对于上述表达式有(n-2)(n-1)/2种加括号的情况，设输入字符串为s,那么只要找出可以加‘(’的下标集合b1,和加')'的下标集合b2,易得b1=b2=n-1（对自己加括号是毫无意义的）,那么加括号的方法总数就是n-1+n-2+.……

[解决办法]
 static double Calculate(double o1, double o2, String oprt)  
       {  
           double result = Int32.MaxValue; //error result  
    
           switch (oprt)  
           {  
               case "+":  
                   result = o1 + o2;  
                   break;  
               case "*":  
                   result = o1 * o2;  
                   break;         
           }  

           return result;  
       }  
    
       /** 
       * 整理指定中缀表达式  
 
       */ 
       private String Trim(String expression)  
       {  
           // 去除表达式中的空格和等号  
           expression = expression.Replace(" ", "").Replace("=", "");  
    
           // 补完右括号  
           int openCount = 0;  
           int closeCount = 0;  
    
           foreach (char ch in expression)  
               switch (ch)  
               {  
                   case '(':  
                       openCount++;  
                       break;  
                   case ')':  
                       closeCount++;  
                       break;  
               }  
    
           if (openCount &gt; closeCount)  
               expression += new String(')', openCount - closeCount);  
    
           return expression;  
       }  
    
       /** 
        * 分离操作符和操作数 
        */ 
       private Queue&lt;String&gt; Split(String expression)  
       {  
           String[] oprt = { "+", "*", "/", "%", "^", "(", ")" };  
           //String[] oprtRegex = { @"\+", @"\*", "/", "%", @"\^", @"\(", @"\)" };  
    
           expression = Trim(expression);  
    
           //foreach (String o in oprtRegex)  
    
           // 右括号后面的减号必为操作符  
           expression = Regex.Replace(expression, @"(?&lt;=\))-", " - ");  
    
           // 两个数字之间的减号亦必为操作符  
           expression = Regex.Replace(expression, @"(?&lt;=\d)-(?=\d)", " - ");  
    
           // 在负号前加上空格以便分割  
           expression = expression.Replace("-", " -");  
    
           // 其他操作符两边都加上空格以便分割  
           foreach (String o in oprt)  
               expression = expression.Replace(o, " " + o + " ");  
    
           //Console.WriteLine(expresion);  
    
           // 将空白字符作为分割符进行切割  
           String[] split = Regex.Split(expression, @"\s+");  
    
           // 去除空白元素  
           Queue&lt;String&gt; result = new Queue&lt;string&gt;();  
           foreach (String str in split)  
               if (str.Length &gt; 0)  
                   result.Enqueue(str);  
    
           result.Enqueue(SIGN_CHAR);  
    
           return result;  
       }  
    
       /** 
        * 返回指定操作符的优先级 
        */ 
       static int PriorityOf(String oprt)  
       {  
           int priority = Int32.MaxValue;//error result  
    
           switch (oprt)  
           {  
               case "+":   
                   priority = PLUS_PRIORITY;  
                   break;  
               case "*":    
                   priority = MULTIPLY_PRIORITY;  
                   break;  
               case "(":  
                   priority = OPEN_PARENTHESES_PRIORITY;  
                   break;
               case SIGN_CHAR:
                   priority = SIGN_PRIORITY;
                   break;  
           }  
           return priority;  
       }  

   }
}

结果：

[解决办法]
凑合写了一个

C# codeusing System;using System.Numerics;namespace CSharpTest{    class Program    {        public static void Main()        {            int[] Items = new int[] { 8, -9, -1, 2, -7 };            BigInteger[, ,] Matrix = new BigInteger[Items.Length, Items.Length, 2];            for (int i = 0; i &lt; Items.Length; i++)            {                for (int j = 0; j + i &lt; Items.Length; j++)                {                    int start = j;                    int end = i + j;                    if (i == 0)                        Matrix[start, end, 0] = Matrix[start, end, 1] = Items[start];                    else                    {                        Matrix[start, end, 0] = int.MinValue;                        Matrix[start, end, 1] = int.MaxValue;                    }                    for (int k = start; k &lt; end; k++)                    {                        Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 0] + Matrix[k + 1, end, 0]);                        Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 0] * Matrix[k + 1, end, 0]);                        Matrix[start, end, 0] = Max(Matrix[start, end, 0], Matrix[start, k, 1] * Matrix[k + 1, end, 1]);                        Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 1] + Matrix[k + 1, end, 1]);                        Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 0] * Matrix[k + 1, end, 1]);                        Matrix[start, end, 1] = Min(Matrix[start, end, 1], Matrix[start, k, 1] * Matrix[k + 1, end, 0]);                    }                }            }            Console.WriteLine(Matrix[0, Items.Length - 1, 0]);            Console.ReadKey();        }        public static BigInteger Max(BigInteger a, BigInteger b)        {            return a &gt; b ? a : b;        }        public static BigInteger Min(BigInteger a, BigInteger b)        {            return a &lt; b ? a : b;        }    }}

【C# 每日一题7】求最大的结果,该怎么

热点推荐