CareerCup

A variation of the matrix chain multiplication should work.
Let the number at each vertex and the (clockwise) next edge be a single element.

struct element {
      int num;
      char op;
}pol[N];

Initialize a 2D matrix m[NxN]

Let m[i,i] = pol[i] for 1 <= i <= N

Let m[i,j] be the maximum value that can be achieved from the subset of elements from index i to index j.

Using the recursive equation :
m[i,j] = max { m[i,k] [operation for element at index k] m[k+1,j] } :: for 1 <= i <= k <= j <= N

This would give the maximum value if the list was linear, but since it is a circular linked list, repeat the entire procedure for the different start points in the circular linked list.

Example: given a quad, (1)--e1(+)--(2)--e2(*)--(-2)--e3(*)--(3)--e4(+)--(1). Removing edge e3 will result in a triangle: (1)--e1(+)--(2)--e2(*)--(-6)--e4(+)--(1).

It reminds me matrix-chain-multiplication but with start point at any vertex. Complexity of matrix-chain-multiplication is O(n^3) so the complexity of this algorithm is O(n^4). Here is algorithm:

int result(int[] vertices, Op[] edges) {
		int [][] dp = null;// initialize with -Integer.min_value and i,i with vertices [i]
		int n = vertices.length;
		int result = Integer.MIN_VALUE;
		for (int startVertex = 0; startVertex < n; startVertex++) {
			for (int length = 2; length <= n; length++) {
				for (int first = startVertex; first <= n - length + startVertex; first++) {
					int last = first + length - 1;
					int max = Integer.MIN_VALUE;
					for (int divider = first; divider < last; divider++) {
						max = Math.max(max, edges[first % n].exec(dp[first % n][divider % n], dp[(divider + 1) % n][last % n]));
					}
					dp[first][last] = max;
				}
			}
			
			result = Math.max(result, dp[startVertex][(startVertex + n) % n]);
		}
		
		return result;
	}

Assuming this would be kept in a circular linked list, traverse it once and collapse vertices as you see addition operation. After the first pass you will be left with only multiplication edges. In the second pass do the multiplications and the result is what you are looking for.

seems like a NP problem. Can be solved using recusrsion:
Repeat for each edge: collapse edge, call recursively, restore edge.
The answer is the maximum value returned from all the recursive calls in the loop above.
Complexity: O(N!) Space: O(N)

A circular variant of matrix chain multiplication algorithm can be used. In the original solution, in the N*N array (say A), only cells with i <= j are filled, but here we would like to fill cells for which i>j as well.

Recursive definition:
V[0...N-1] - list of values on the vertices.
O[0...N-1] - list of operators.. Oi is the operator on edge connecting vertices i and i+1.

A[i, j] = Vi                  if i == j
         = max { Ok(A[i,k], A[k,j] }  for k: i->j if i<j
                                                     for k:i->N-1 and k:0->j if j<i

Example: V[-2, 3, 2, 4, -8, 5], O[*, +, *, *, +, *]

A:

iter1
-2 0 0 0  0 0
 0 3 0 0  0 0
 0 0 2 0  0 0 
 0 0 0 4  0 0 
 0 0 0 0 -8 0 
 0 0 0 0  0 5 

iter2:
-2 0 0    0    0   -10
-6 3 0    0    0      0
 0 5 2    0    0      0 
 0 0 8    4    0      0 
 0 0 0 -32  -8      0 
 0 0 0     0 -3      5

and so on to fill the whole table. And the maximum element in the filled array is the answer.
O(n*n) time+ O(n*n) space.

I think matrix chain multiplication algorithm can be applied in this problem. Comparing to classical dynamic program method, what we need to do here is to store two values for a random combination[i, j]: the positive number with largest abstract value; the negative number with largest abstract value.(Since we need to handle * and + operations)

is there any operator presidency means to say we can go sequential or first multiplication then addition ..

dynamic programming will give you the solution in O(n*n) + O(n*n) complexity
Here is solution :
lets say you have hexagon( with following 1(15)-2(9)-3(12)-4(1)-5(7)-6(12)-1(15)), where values written in *()* is the value at each node
Now make a 2d matrix of size 6x6, write these values in the main diagonal,

15.24.36..37.44.56
.......9...21.22.29.41
............12.13.20.32
....................1..8..20
........................7..19
.............................12

the right most corner value is the answer

Can we not do this as a MST Problem ? Minimum spanning tree ?

The last step is not clear what is the expectation.
But I think the you should make all the + operations first and after the * to calculate the maximum summary. (assumption the numbers>1 and all integers.)
So, Do first all the + operations. It's just 0(n).
After that we will have only * operations. Do all of them. O(n)
You will have the result. With O(2n)= O(n).

The way I see it is as follows:

- call the vertices of the polygon P: p0, p1, ..., pn
- think of P as a vertex V0
- from this vertex V0 you have n edges, each one going to a n different vertices: V1_1, V1_2, .., V1_n
- V1_i is the polygon resulting from removing edge i from P
- the edge between V0 and V1_i is the result of the operation marked by edge i: oper(pi-1, pi)
- from each V1_i you have n-1 new edges to n-1 new vertices
- continue forming the "super graph" until you have a polygon of 2 edged with 2 vertices

What we are looking for is for the longest path with the heaviest weight.

In this super graph we have n! vertices, and the problem is NP.

I think we can use just greedy approach. I.e. for polygon with k edges find a pair (p, q) which produces the maximum number: (p ,q) = max ({i operation j : i, j - adjacent edges)

Then just call a recursion on polygons:
1. Let function CollapseMaxPair( P(k) ) - gets polygon with k edges and returns 'collapsed' polygon with k-1 edges
2. Then our recursion:

P = P(N);
     Releat until two edges left
         P =  CollapseMaxPair( P )
     maxvalue = max ( two remained values)

What do you think?

If the numbers are a and b then:
- if a <= b <= 0 --> use *
- if a < 0 < b --> use +
- if 0 == a and 0<= b --> use +
- if 1 == a and 1<= b --> use +
- else /* 1 < a <=b */ --> use *

And then does not matter which edge you start with.

1. choose 1 gabage value (for the last operation).
- if the number of (-) vertexs is 2k, the gabage vertex should be the smallest (+) vertex.
- if the number of (-) vertexs is 2k+1, the gabage vertex should be the biggest (-) vertex.
2. if the vertex value is either 0 or 1 use '+'
3. else use '*' operator..
(2.3 from Karthik Vvs's)

You can do this in O(2n).
Start at any node. Push back that node's value on to a vector. When you traverse to the next node, perform the operation that takes you to that node on every number in the vector with the value of the next node. Repeat until you are back at your starting node.
The value at index 1 of your vector is the value for the starting node, it's your current best_max. Then, for each entry in the vector, move to the next node in the polygon, performing the correct operation to get you to that node on every entry in the vector. Before you move on to the next vector entry, compare against your best_max. best_max will have the answer.

traverse each node and merge edges in this order.
1. with both vertices -ve and (*) op, as this will increase the +ve vertices in polygon.
2. with one vertices +ve and one -ve and op (+). this will try to nullify the -ve of nodes.
3. with one vertices +ve and one -ve and op (*).
4.with both vertices -ve and (+) op,

as in 4 pass we will merge all the edges with maximum result.

As the question is to find the maximum value..
1.if the vertex value is either 0 or 1 use '+'
2.else use '*' operator..
3.for example if the vertices values are in order 0,4,1,3,2,5..then the max result is ((0+4)+1)*3*2*5
code is as follows:

int result=0;
  for each vertex in polygon P:
        if(vertex.data==0 || vertex.data==1)res+=vertex.data; //considering vertex as a node 
        else res*=vertex.data;
  return res;

The easiest solution I could find was, first perform all (+) operations, followed by (*) operations to get the max number.

e.g. 1(+) - 2(*) - 3(*) - 2(+) - 5(+) - 3(*)

Ans - (1+2)*3*(2+5+3)