Flip cards to get maximum sum

Question

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?

My Code : Am not able to find problem till yet

#include<bits/stdc++.h>
using namespace std;
int solve(std::vector<int> const & numbers)
{
    int min_so_far  = numbers[0], min_ending_here = numbers[0];
    size_t begin = 0;
    size_t begin_temp = 0;
    size_t end = 0;
    for(size_t i = 1; i < numbers.size(); i++)
    {
            if(min_ending_here > 0)
            {
                    min_ending_here = numbers[i];
                    begin_temp = i;
            }
            else
            {
                    min_ending_here += numbers[i];
            }

            if(min_ending_here <= min_so_far )
            {
                    min_so_far  = min_ending_here;
                    begin = begin_temp;
                    end = i;
            }
    }
    int sum=0;
    for(int i=0;i<begin;i++){
        sum+=numbers[i];
    }
    for(int i=begin;i<=end;i++){
        sum-=numbers[i];
    }
    for(int i=end+1;i<numbers.size();i++){
        sum+=numbers[i];
    }
    return sum;

}
int main(){
int n;
cin>>n;
vector<int> arr;
for(int i=0;i<n;i++){
    int x;
    cin>>x;
    arr.push_back(x);
}

  cout<<solve(arr)<<"\n";
}

Answer 1

The only thing you need to find is the minimum sum that you can form with consecutive numbers, and then flip those. In your example, the last three numbers add up to -7, and there is no other set of consecutive number which have a lower sum, so flipping them does the trick. If the minimum sum is non negative, then you don't need to flip them.

Now, what I described above is a well known algorithm, and it is called Kadane's algorithm, which can be solve in O(n), notice that the Wikipedia link shows how to do it for the maximum, but you can easily modify it to find the minimum.