Given a string S of digits(0-9).Find the maximum value that can be obtained from the string by putting either '*' or '+' operators in between the digits while traversing from left to right of the string and picking up a single digit at a time.
Example 1:
Input: 
S="01230"
Output: 
9
Explanation: 
we have 01230.We traverse from 
left and pick zero.Now we encounter '1'. 
We see if 0*1 gives maximum or 0+1.Now we 
have ans=1.Now we traverse further.We 
encounter '2'.Now we see whether 1*2 gives 
max or 1+2.Now we have ans=3.Now we 
traverse further. We encounter'3'.
We see if 3*3 gives max or 3+3.
The ans is now 9.Now we traverse further. 
We encounter 0, we see if 9+0 gives max or 
9*0. The ans is now 9. We've traversed the
whole string so we stop.
Example 2:
Input: 
S="891"
Output: 
73
Explanation:
We start at 8,then go to
9 and see whether 8+9 is greater or
8*9.Now we have 72,we traverse 
forward and check whether 72*1 is 
greater or 72+1.In this way, we get 
the answer as 73.
Your Task:
You don't need to read input or print anything. Your task is to complete the function MaximumIntegerValue() which takes the string S as input parameter and returns the maximum integer value that can be created using given procedures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 <= |S| < 20
S contains only digits from 0 to 9
Leading 0's maybe present.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def MaximumIntegerValue(self,S):
        #code here

Solutions:
class Solution:

	def MaximumIntegerValue(self, S):
		a = int(S[0])
		for i in range(1, len(S), 1):
			b = int(S[i])
			a = max(a + b, a * b)
		return a


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) > 1:
			if S[0] == '0' or S[0] == '1' or S[1] == '0' or (S[1] == '1'):
				result = int(S[0]) + int(S[1])
			else:
				result = int(S[0]) * int(S[1])
			if len(S) > 2:
				for i in range(2, len(S)):
					if S[i] == '0' or S[i] == '1' or result == 1 or (result == 0):
						result += int(S[i])
					else:
						result *= int(S[i])
			return result
		else:
			return int(S[0])


class Solution:

	def MaximumIntegerValue(self, S):
		max_s = 0
		max_p = 1
		for i in range(len(S)):
			max_s += int(S[i])
			max_p *= int(S[i])
			maxx = max(max_s, max_p)
			max_s = max_p = maxx
		return maxx


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) < 2:
			return S
		ans = ''
		f = int(S[0])
		for i in range(1, len(S)):
			s = int(S[i]) * f
			p = int(S[i]) + f
			ans = max(s, p)
			f = ans
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) == 1:
			return S[0]
		a = int(S[0])
		ans = 0
		for i in range(1, len(S)):
			b = a * int(S[i])
			c = a + int(S[i])
			if b > c:
				ans = b
			else:
				ans = c
			a = ans
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) == 1:
			return int(S[0])
		k = max(int(S[0]) * int(S[1]), int(S[0]) + int(S[1]))
		S = S[2:]
		for i in range(len(S)):
			l = max(k * int(S[i]), k + int(S[i]))
			k = l
		return k


class Solution:

	def MaximumIntegerValue(self, S):
		l1 = list(S)
		string = ''
		for index in range(len(S) - 1):
			if int(l1[index]) + int(l1[index + 1]) > int(l1[index]) * int(l1[index + 1]):
				k = int(l1[index]) + int(l1[index + 1])
				l1.pop(index + 1)
				l1.insert(index + 1, k)
			else:
				k = int(l1[index]) * int(l1[index + 1])
				l1.pop(index + 1)
				l1.insert(index + 1, k)
		k1 = list(map(int, l1))
		return max(k1)


class Solution:

	def MaximumIntegerValue(self, S):
		sum = 0
		pro = 1
		for i in range(len(S)):
			sum += int(S[i])
			pro *= int(S[i])
			max1 = max(sum, pro)
			sum = pro = max1
		return max1


class Solution:

	def MaximumIntegerValue(self, S):
		an = int(S[0])
		for i in range(1, len(S)):
			mult = an * int(S[i])
			plus = an + int(S[i])
			if mult > plus:
				an = mult
			else:
				an = plus
		return an


class Solution:

	def MaximumIntegerValue(self, s):
		total = int(s[0])
		for i in range(len(s) - 1):
			b = s[i + 1]
			c = total + int(b)
			d = total * int(b)
			total = max(c, d)
		return total


class Solution:

	def MaximumIntegerValue(self, S):
		s = S[0]
		for i in S[1:]:
			a = int(s) + int(i)
			m = int(s) * int(i)
			p = max(a, m)
			s = p
		return s


class Solution:

	def MaximumIntegerValue(self, s):
		x = int(s[0])
		for i in range(1, len(s)):
			a = x + int(s[i])
			b = x * int(s[i])
			ans = max(a, b)
			x = ans
		return x


class Solution:

	def MaximumIntegerValue(self, s):
		length = len(s)
		if length >= 2:
			a = max(int(s[0]) * int(s[1]), int(s[0]) + int(s[1]))
			for i in range(2, length):
				a = max(a * int(s[i]), a + int(s[i]))
			return a
		else:
			return s


class Solution:

	def MaximumIntegerValue(self, S):
		addition = 0
		multiplication = 1
		for i in range(len(S)):
			addition += int(S[i])
			multiplication *= int(S[i])
			if addition > multiplication:
				multiplication = addition
			else:
				addition = multiplication
		maxx = addition = multiplication
		return maxx


class Solution:

	def MaximumIntegerValue(self, S):
		(add, product) = (0, 1)
		for i in range(len(S)):
			add += int(S[i])
			product *= int(S[i])
			result = max(add, product)
			product = result
			add = result
		return result


class Solution:

	def MaximumIntegerValue(self, S):
		chars = [char for char in S]
		ans = int(chars[0])
		for char in chars[1:]:
			num = int(char)
			if ans + num >= ans * num:
				ans = ans + num
			else:
				ans = ans * num
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		sump = int(S[0])
		for i in range(1, len(S)):
			sump = max(sump * int(S[i]), sump + int(S[i]))
		return sump


class Solution:

	def MaximumIntegerValue(self, s):
		ans = -9999999999
		if len(s) == 1:
			return int(s)
		if len(s) == 2:
			return max(int(s[0]) * int(s[1]), int(s[0]) + int(s[1]))
		else:
			ans = max(int(s[0]) * int(s[1]), int(s[0]) + int(s[1]))
			for i in range(2, len(s)):
				ans = max(ans * int(s[i]), ans + int(s[i]))
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		S = list(map(int, S))
		tulos = S[0]
		for i in range(1, len(S)):
			if tulos + S[i] > tulos * S[i]:
				tulos += S[i]
			else:
				tulos = tulos * S[i]
		return tulos


class Solution:

	def MaximumIntegerValue(self, S):
		result = 0
		for i in range(len(S)):
			result = max(result * int(S[i]), result + int(S[i]))
		return result


class Solution:

	def MaximumIntegerValue(self, S):
		s = 0
		p = 0
		for i in range(len(S)):
			s += int(S[i])
			p *= int(S[i])
			r = max(s, p)
			s = p = r
		return r


class Solution:

	def MaximumIntegerValue(self, S):
		maxs = 0
		maxp = 1
		for i in range(len(S)):
			maxs += int(S[i])
			maxp *= int(S[i])
			maxx = max(maxs, maxp)
			maxs = maxp = maxx
		return maxx


class Solution:

	def MaximumIntegerValue(self, S):
		num = 0
		for s in S:
			num = max(num * int(s), num + int(s))
		return num


class Solution:
	var = 0

	def MaximumIntegerValue(self, s):
		for x in range(len(s)):
			if x == 0:
				var = int(s[x])
			elif var * int(s[x]) > var + int(s[x]):
				var = var * int(s[x])
			else:
				var = var + int(s[x])
		return var


class Solution:

	def MaximumIntegerValue(self, S):
		ans = 0
		for i in range(len(S)):
			if i != 0:
				mul = f * int(S[i])
				add = f + int(S[i])
				f = max(mul, add)
			else:
				f = int(S[i])
		return f


class Solution:

	def MaximumIntegerValue(self, S):
		val = int(S[0])
		for j in range(1, len(S)):
			k = int(S[j])
			if val * k > val + k:
				val *= k
			else:
				val += k
		return val


class Solution:

	def MaximumIntegerValue(self, s):
		sum = int(s[0])
		for i in range(1, len(s)):
			v = int(s[i])
			if v + sum > v * sum:
				sum = v + sum
			else:
				sum = v * sum
		return sum


class Solution:

	def MaximumIntegerValue(self, S):
		self.s_ele = list(map(int, S))
		l_no = int(S)
		for ele in range(len(self.s_ele) - 1):
			if ele < 1:
				self.op_mul = self.s_ele[ele] * self.s_ele[ele + 1]
				ele_mul = self.op_mul
				self.op_add = self.s_ele[ele] + self.s_ele[ele + 1]
				ele_add = self.op_add
				if ele_mul > ele_add:
					l_no = ele_mul
				else:
					l_no = ele_add
			elif ele == 1:
				ele_mul = l_no * self.s_ele[ele + 1]
				ele_add = l_no + self.s_ele[ele + 1]
				if ele_mul > ele_add:
					l_no = ele_mul
				else:
					l_no = ele_add
			elif ele >= 2:
				if ele == 2:
					ele_mul = l_no * self.s_ele[ele + 1]
					ele_add = l_no + self.s_ele[ele + 1]
					if ele_mul > ele_add:
						l_no = ele_mul
					else:
						l_no = ele_add
				else:
					ele_mul = l_no * self.s_ele[ele + 1]
					ele_add = l_no + self.s_ele[ele + 1]
					if ele_mul > ele_add:
						l_no = ele_mul
					else:
						l_no = ele_add
		return l_no


class Solution:

	def MaximumIntegerValue(self, s):
		x = 0
		for i in s:
			if x * int(i) > x + int(i):
				x *= int(i)
			else:
				x += int(i)
		return x


class Solution:

	def MaximumIntegerValue(self, S):
		c = 0
		c1 = 1
		for i in range(len(S)):
			c = c + int(S[i])
			c1 = c1 * int(S[i])
			if c > c1:
				r = c
			else:
				r = c1
			c = r
			c1 = r
		return r


class Solution:

	def MaximumIntegerValue(self, S):
		prev = int(S[0])
		for i in range(1, len(S)):
			cand1 = prev * int(S[i])
			cand2 = prev + int(S[i])
			if cand1 >= cand2:
				prev = cand1
			else:
				prev = cand2
		return prev


class Solution:

	def MaximumIntegerValue(self, S):
		ans = int(S[0])
		for i in S[1:]:
			i = int(i)
			if i == 0 or i == 1 or ans == 0 or (ans == 1):
				ans += i
			else:
				ans *= i
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) < 2:
			return S
		sm = max(int(S[0]) + int(S[1]), int(S[0]) * int(S[1]))
		for x in range(2, len(S)):
			r = int(S[x])
			sm = max(sm + r, sm * r)
		return sm


class Solution:

	def MaximumIntegerValue(self, S):
		a = 0
		b = 0
		max = 0
		for i in S:
			a = int(i) + max
			b = int(i) * max
			if a >= b:
				max = a
			else:
				max = b
		return max


class Solution:

	def MaximumIntegerValue(self, str):
		res = ord(S[0]) - 48
		for i in range(1, len(S)):
			if str[i] == '0' or str[i] == '1' or res < 2:
				res += ord(str[i]) - 48
			else:
				res *= ord(str[i]) - 48
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		s = list(S)
		mul = 1
		add = 0
		for i in range(len(s)):
			s[i] = int(s[i])
			mul *= s[i]
			add += s[i]
			r = max(mul, add)
			mul = r
			add = r
		return r
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		res = int(S[0])
		for s in S[1:]:
			d = int(s)
			res = max(res + d, res * d)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, s):
		(a, p) = (0, 1)
		for i in range(len(s)):
			a += int(s[i])
			p *= int(s[i])
			r = max(a, p)
			p = r
			a = r
		return r
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		ans = int(S[0])
		for i in range(1, len(S)):
			if S[i] == '0' or S[i] == '1' or ans == 1:
				ans += int(S[i])
			else:
				ans *= int(S[i])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		res = int(S[0])
		for i in range(1, len(S)):
			tmp = int(S[i])
			localsum = res + tmp
			localmul = res * tmp
			if localsum > localmul:
				res = localsum
			else:
				res = localmul
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		max_val = int(S[0])
		for ele in S[1:]:
			max_val = max(max_val + int(ele), max_val * int(ele))
		return max_val
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, s):
		n = len(s)
		if n == 1:
			return int(s)
		elif n < 1:
			return 0
		max_num = max(int(s[0]) + int(s[1]), int(s[0]) * int(s[1]))
		if n == 2:
			return max_num
		for i in range(2, n):
			x = int(s[i])
			max_num = max(x + max_num, x * max_num)
		return max_num
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		t = 0
		n = len(S)
		for i in range(n):
			k = int(S[i])
			if t + k >= t * k:
				t = t + k
			else:
				t = t * k
		return t
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		k = int(S[0])
		for i in range(1, len(S)):
			x = k * int(S[i])
			y = k + int(S[i])
			k = max(x, y)
		return k
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		length = len(S)
		index = 0
		total = 0
		while index < length:
			number = int(S[index])
			if total * number > total + number:
				total *= number
			else:
				total += number
			index += 1
		return total
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		lst = list(S)
		for itr in range(len(lst) - 1):
			if lst[itr] in ['0', '1'] or lst[itr + 1] in ['0', '1']:
				lst[itr + 1] = str(int(lst[itr]) + int(lst[itr + 1]))
			else:
				lst[itr + 1] = str(int(lst[itr]) * int(lst[itr + 1]))
		return int(lst[-1])
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		if len(S) == 1:
			return S
		s = [int(i) for i in S]
		x = s[0] * s[1]
		y = s[0] + s[1]
		if x > y:
			ans = x
		else:
			ans = y
		for i in range(2, len(s)):
			if ans * s[i] > ans + s[i]:
				ans = ans * s[i]
			else:
				ans = ans + s[i]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		ans = 0
		for i in S:
			ans = max(ans * int(i), ans + int(i))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.MaximumIntegerValue(S))


class Solution:

	def MaximumIntegerValue(self, S):
		n = len(S)
		if len(S) == 1:
			return S
		ans = max(int(S[0]) * int(S[1]), int(S[0]) + int(S[1]))
		for i in range(2, n):
			maxx = max(ans * int(S[i]), ans + int(S[i]))
			if maxx > ans:
				ans = maxx
		return ans


class Solution:

	def MaximumIntegerValue(self, S):
		result = int(S[0])
		for i in range(1, len(S)):
			result1 = result * int(S[i])
			result2 = result + int(S[i])
			result = max(result1, result2)
		return result


class Solution:

	def MaximumIntegerValue(self, S):
		s = S
		l = int(s[0])
		for i in range(1, len(s)):
			l = max(l * int(s[i]), l + int(s[i]))
		return l


class Solution:

	def MaximumIntegerValue(self, S):
		res = 0
		for val in S:
			if res * int(val) >= res + int(val):
				res = res * int(val)
			else:
				res = res + int(val)
		return res


class Solution:

	def MaximumIntegerValue(self, S):
		val = 0
		if len(S) == 1:
			return S[0]
		elif len(S) == 2:
			if int(S[0]) + int(S[1]) > int(S[0]) * int(S[1]):
				val += int(S[0]) + int(S[1])
			else:
				val = 1
				val *= int(S[0]) * int(S[1])
			return val
		else:
			val = 0
			if int(S[0]) + int(S[1]) > int(S[0]) * int(S[1]):
				val += int(S[0]) + int(S[1])
			else:
				val = 1
				val *= int(S[0]) * int(S[1])
			for i in range(2, len(S)):
				if val + int(S[i]) > val * int(S[i]):
					val += int(S[i])
				else:
					val *= int(S[i])
			return val


import sys

class Solution:

	def MaximumIntegerValue(self, S):
		(a, p) = (0, 1)
		for i in range(len(S)):
			a += int(S[i])
			p *= int(S[i])
			r = max(a, p)
			p = r
			a = r
		return r


class Solution:

	def MaximumIntegerValue(self, s):
		ans = int(s[0])
		for x in s[1:]:
			if ans * int(x) > ans + int(x):
				ans = ans * int(x)
			else:
				ans = ans + int(x)
		return ans