Can someone at least give me some hint ?

Given that the numbers are only positive and you only have the multiplication and addition operators you can devise a simple dynamic programming solution.

First, given that you do the bracketing from right to left, you can reverse your lits of numbers. Then, you can setup a look up table of size [Size of sequence of numbers] X [Size of sequence of operators]. The value of table[i][j] will indicate tha maximum value of the expression if you had only the first i numbers (last i before reversing the list) from the list and the first(last) j operators from the list of operators.

The value of table[i][j] is obtained by looking at the values of table[i-1][j-1] and table[i-1][j] denoting that you either add the next number in the list to the expression or you don't.

I think this should be enough of a hint. Do ask more questions if you are unsure how to set up the whole solution.

It may be possible to improve the computational efficiency of solving this problem by comparing the result of the two expressions (x*y) and (x+y) for a given pair of integer x and y. Suppose that f(x,y) = (x*y)-(x+y) = (x-1)*(y-1)-1.

It follows that f(x,y) >= 0, i.e. x*y >= x+y, when min(x,y) >= 2.

Let K, N and M be the size of the multi-set of binary operators, the size of the multi-set of integers and the number of ones in the latter set, respectively. Let L = K+1 be the number of integers in the optimal expression. It follows from the previous result that the optimal expression should have at most P = L-min(N-M,L) ones.

In your example, K = 2, N = 5, M = 2, L = 3, N-M = 3, and P = 0. It follows that the optimal expression should have no ones, i.e. composed of the numbers 3, 2, and 4 only.

Another possibility to improve the computational efficiency is to compute the histogram h(x) of the multi-set of integers, the number of times that x exists in the multi-set, and use it to compute g(x), the cumulative count of integers >= x in the multi-set. Any integer x whose g(x) < L should exist in the optimal expression.

Suppose that u is largest integer such that g(u) >= L, and that H = h(u). Then, u should be the smallest integer to exist in the optimal expression. Suppose also that v is the smallest integer to exist in the optimal solution such that g(v) < L, and that V = g(v). Then, the number of times that u should appear in the optimal solution is U=L-V, It is imperative that H >= U. The number of all possible ways to select U instances of u out of all H instances in the multi-set is C(H,U), where C(n,r) is the binomial coefficient.

The following is a C++17 code to compute the numbers that should exist in the optimal solution from the histogram h(x) function and the cumulative count function g(x)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int H, K, L, M, N, U, V = 0, a, g = 0, u, v; string op; 
    
    cin >> K >> N >> op, L = K + 1; 
    
    map< int, vector< int > > h; set< pair< int, int > > exists; 
    
    for( int i = 0; i < N; i++ )
        cin >> a, h[ a ].push_back( i );
        
    auto it = h.crbegin(), iu = h.crend(), iv = it; M = h[ 1 ].size(); 
    
    while( iv != iu && ( V = g, g += iv->second.size() ) < L )
        iv++; 
    
    for( auto iw = it; iw != iv; v = iw->first, iw++ )
        for( auto i: iw->second )
            exists.emplace( i, iw->first );
    
    u = iv->first, U = L - V, P = L - min(N-M,L);
    
    auto &z = iv->second; H = z.size();  
    
    cout << "v = " << v << ", V = " << V << ", M = " << M << ", P = " << P << endl;

    for( auto p: exists )
        cout << p.second << " at index " << p.first << endl;
    
    cout << U << "-out-of-" << H << " instance(s) of " << u <<  " at index(es)" << endl;
    
    for( auto q: z )
        cout << q << ' ';
}

The input to the program for your example is:

2 5

*+

1 3 2 1 4

and the program output is:

v = 3, V = 2, M = 2, P = 0

3 at index 1

4 at index 4

1-out-of-1 instance(s) of 2 at index(es)

2

=====

Used: 15 ms, 3264 KB

Hope that these observations help.