You are not logged in. Please login at www.codechef.com to post your questions!

×

CHGM1 - Editorial

PROBLEM LINK:

Practice

Contest

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.

Algorithm:

Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if max_ending_here is less than 0 max_ending_here = 0 (c) if max_so_far is less than max_ending_here max_so_far = max_ending_here return max_so_far

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

dshahid380_'s gravatar image

3★dshahid380_
314
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×862
×94
×21
×5

question asked: 15 Mar, 13:08

question was seen: 70 times

last updated: 2 days ago