Flip cards to get maximum sum 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?
 A: There will be groups of cards with only positive values ($x_i > 0$) in between groups of cards with only non-positive values ($x_i \leq 0$).
You can use this to limit the number of trials you consider.  The motivation is that there is no benefit to including positive cards on the ends of the group of cards you're going to flip.  They only hurt.  Likewise, you'll want to include entire groups of negative cards at the ends, because that will only help.
Step through the cards until you hit a negative value.  Add up the cards' values until you hit a positive one.  Record the sum, and the indices of the start and end cards.
Now step through the cards, adding them up along the way until you hit another negative.  Record the sum and the indices of the start and end cards.
Repeat the process until you go through all the cards.  You'll end up with a number of negative and positive sums: $S_{i}^{-}, S_{i}^{+}.$  Any positive groups at either end shouldn't be flipped, so we really only need to consider $$S_{1}^{-}, S_{1}^{+}, S_{2}^{-}, S_{2}^{+}, \cdots S_{n-1}^{-}, S_{n-1}^{+}, S_{n}^{-}.$$
To find the global minimum (which, when flipped, would give the largest gain in the value), find the minimum of all possible sets of cards that have $k-1$ positive sums in between $k$ negativs sums, for $1 \leq k \leq n$.
First find $min(S_i^-)$.  Then find $min(S_i^-S_i^+S_{i+1}^-)$.  Then find $min(S_i^-S_i^+S_{i+1}^-S_{i+1}^+S_{i+2}^-)$, and so on.
The minimum of all of these are the cards that you should flip.
A: 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). 
