Question

You are given a sequence of positive real numbers a[1..n]. You can now add ‘+’ and ’×’ signs between these numbers, and your goal is to generate an expression that has the largest value. As an example, if a = {2, 3, 0.5, 2}, then you should output the expression 2 × 3 + 0.5 + 2 = 8.5. This is larger than any other expression (e.g. 2 × 3 × 0.5 × 2 = 6, 2 + 3 + 0.5 + 2 = 7.5, 2 + 3 ∗ 0.5 + 2 = 5.5 ...). You must add either a ‘+’ or a ‘×’ between two consecutive numbers, and you are not allowed to change the ordering of the numbers or add brackets. As usual the expression is evaluated to first compute the products and then the sum. Design an algorithm that runs in time O(n ² ) and outputs the largest possible value. For this problem you can assume all additions, multiplications and comparisons of real numbers can be done in O(1) time. This needs to be in C++ and Please explain the process in comments. Thank you!

Answer 1

Below is the C++ program:

#include <iostream>

using namespace std;

int main()
{
int n; // to input the total numbers in the array

cout<<"Enter the number of Numbers in the array: ";
cin>>n;

double arr[n];// array to store the numbers

cout<<"Enter the numbers\n";
  
for(int i=0;i<n;i++)
{
cin>>arr[i]; // stores each element on ith position i.e. [0....n-1]
}
  
double ans=0; // Initialize our answer with 0
  
/* Logic is to find all the numbers which are greater than 1 and find there continues multiplication first,
as 1+1=2 and 1*1=1 this means that the no. which are less than or equal to 1 will always give
greater value in addition than in multiplication
*/
for(int i=0;i<n-1;i++)// as we are comparing two adjacent values therefore loop will run till [0...n-2]  
{
if(arr[i]>1 && arr[i+1]>1)
{
int temp=arr[i]*arr[i+1]; // stores multiple of two numbers adjacent to each other

arr[i]=-1;// replaces previous value to -1 so that we won't traverse it again
arr[i+1]=temp;// stores continuous multiplication value to the latest array value
// so it will be used in our next iteration
  
}
  
}
/* now according to the example the modified array will be like [-1,6,0.5,2], now we have to add all the numbers
which are not -1*/
  
for(int i=0;i<n;i++)
{
if(arr[i]!=-1)
{
ans+=arr[i]; // ans stores sum of all the values of the array
}
}

cout<<"The largest number possible is: "<<ans;
return 0;
}

OUTPUT:

The complexity is O(n2) as we are iterating loop two times, first to find continues multiple and then to find sum of all the numbers.