PROBLEM LINK:Author: Md Shahid Tester: Arkapravo Ghosh Editorialist: Md Shahid DIFFICULTY:Easy PREREQUISITES:Array and loop PROBLEM:You need to find longest sum contiguous subarray. EXPLANATION:At the end of the game everyone has some point it may be either positive or negative. We need to find the maximum sum of contigous elements. This type of problem is easily solved by the Kadane's algorithm.
The purpose of Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far AUTHOR'S AND EDITORIALIST'S SOLUTIONS:Author's and editorialist’s solution can be found here.
This question is marked "community wiki".
asked 15 Mar, 13:08
