Bit-by-Bit: Solve and get sweets

Problem Code: GETSWE

Contest Page | CodeChef

Let us try and understand the approach and solution for the question GETSWE. The pre-requisites for solving this question are:

1. Bit manipulation
2. Kadane’s Algorithm

APPROACH :

The question says we have to add the length of the subarray chosen to the final sum we get after getting the sum of the whole array(after taking 1’s complement of that subarray). 1’s complement of a number num is nothing but bitwise not of that number, i.e ~num.

Since we need to add the length of the subarray to the final sum of the array, it is the same as adding 1 to each of the elements in the chosen subarray after taking their 1’s complement. i.e for every element in the chosen sub-array we take its 1’s complement and add ‘1’ to it. That means for every element arr[i] in that subarray we perform arr[i] = ~arr[i] + 1. The value of ~arr[i]+1 is same as -arr[i].

Now the question has reduced to :

Given an array arr[] of N integers, the task is to find the maximum sum of the array that can be obtained by flipping signs of any subarray of the given array at most once.

Now, this is a variation of Kadane’s algorithm.

Go through a detailed explanation of this variation here.

Solution: