Given a string of number. Calculate maximum value using ‘+’ or ‘*’ sign between two numbers in a string

Problem: Given a string of numbers, write a program to find the maximum value from the string, you can add a ‘+’ or ‘*’ sign between any two numbers.

For example:

Input: s = "123401"
Output: ((((1 + 2) * 3) * 4) + 0) + 1) = 37
In above manner we get maximum value.

Input: s = "781"
Output: ((7 * 8) + 1) = 57
In above manner we get maximum value.

Method 1: The idea here is to parse through the input one number at a time and if the number is 0 or 1 then use + else use * .

• n * 0 = 0 but n + 0 = n, which is greater 
• n * 1 = n but n + 1 = n + 1, which is greater 

Following is c++ implementation of the idea.

#include <bits/stdc++.h>
using namespace std;

/* function to get maximum value from string */
int maxVal(string s)
{
    /* store the first number in ans */
    int ans = (s[0] - '0');

    /* traversing the string */
    for(int i = 1; i < s.length(); i++)
    {
        /* if s[i] = 0 || s[i] = 1 || s[i-1] = 0 || s[i-1] = 1, we add */
        if((s[i]-'0') == 0 || (s[i]-'0') == 1 || (s[i - 1]-'0') == 1 || (s[i - 1]-'0') == 0)
        {
            ans += (s[i] - '0');
        }
        else
        {
            /* otherwise use * */
            ans *= (s[i] - '0');
        }
    }

    return ans;
}

/* driver function */
int main()
{
    string s = "123401";
    cout<<maxVal(s);   

    return 0;
}

Output:

37

Time Complexity: O(n)