Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive order only once.
Now we need to flip cards in such a way that sum of number of upper face of cards is maximum.
Example : If N=5 and cards[] be {-2,3,-1,-4,-2} then here answer is 8 as we can flip last 3 cards to get configuration {-2,3,1,4,2} which sum to 8.
My Approach :
Go for each possible way for each ith position as start position and find the maximum.But is their any better solution to this problem?
Best Answer
Since there are $\binom{N}{2} = \Omega(N^2)$ different intervals to possibly flip over, and computing the sum after flipping a given interval involves summing $N$ numbers, the naive algorithm you propose takes either $\Omega(N^3)$ time. With some cleverness, you can improve this to $\Omega(N^2)$ by reusing certain computations.
Here is an algorithm that takes linear time in the number $N$ of cards. Let $c_{i}$ be the number on card $i$. Let $S$ be the current sum of all the numbers on the cards, and let $v_{i,j}$ be the sum of the numbers on the cards between cards $i$ and $j$ inclusive (so in particular, $S=v_{1,n}$). Note that if we flip all the cards between $i$ and $j$, the total sum $S$ changes from $S$ to $S-2v_{i,j}$. We therefore want to find $i$ and $j$ such that $v_{i,j}$ is minimized.
Let $s_{i} = v_{1, i}$; that is, the sum of the first $i$ cards. Note that $v_{i,j} = s_{j} - s_{i-1}$. Moreover, to minimize $v_{i,j}$ while keeping $j$ fixed, we clearly want to choose the $i\leq j$ that maximizes $s_{i-1}$.
Therefore, to minimize $v_{i,j}$, we can use the following algorithm. First compute $s_{j}$ for all $j$ between $1$ and $N$; we can do this in time $O(N)$ by using the fact that $s_{j} = s_{j-1} + c_{j}$. Next, for each $j$ between $1$ and $N$, compute $t_{j} = \max_{i < j} s_{i}$. Again, once we've computed all the $s_{i}$, we can compute all the $t_{j}$ in linear time by noting that $t_{j} = \max(t_{j-1}, s_{j-1})$. Finally, the minimum value of $v_{i,j}$ we want is simply the minimum of $s_{j} - t_{j}$ over all $j$ between $1$ and $n$, which can easily be computed in linear time.
Note: This problem (of computing the minimum/maximum sum of a continuous interval of a sequence of numbers) is a classic problem in CS; the accompanying linear time algorithm sometimes goes by the name of Kadane's algorithm (see http://en.wikipedia.org/wiki/Maximum_subarray_problem).