The Card Game
One day, Fred and his N friends were playing a card game in which each player throws a card with a number written on it. The cards are such that a number X is written on front of the card, and the negative of that number is written on the back of the card. The game has the following rules.
Each of the N players is asked to throw a card. After all the N cards are thrown, Fred has to flip one or more cards in consecutive order, only once.
Your task is to help flip the cards in such a way that the sum of the numbers, on front face of the cards, is the maximum.
Test Case 1
Input :
5
-2 3 -1 -4 -2
Output: 8
Since Fred can flip consecutive cards only once, he chooses to flip the last three cards, which results in the maximum sum (-2 + 3 + 1 + 4 + 2) i.e 8.
Therefore, 8 is returned as the output.
// TODOCheat Ways
It is examination time and as always, the backbenchers are finding ways to cheat in the exam and they need your help. Their teacher is very fond of data structures and has made the seating arrangement in the form of a tree.
There are N students in class numbered from 1, 2 .. N with 1 as the root of this tree. We have K first benchers( teacher's favourites) students in the class. The backbenchers are planning to pass chits in teams but are afraid of the first benchers. If any chit reaches them, they will complain to the teacher.
A cheat way is defined as the path along which a chit can be passed without going through a first bencher. Given the seating arrangement and number of first bencers, your task is to find the longest cheat way possible.
// TODOThis file is created by Kiranpal Singh
For Data Structures and Algorithm snippets, click here