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

×

The maximum subarray problem

0
1

hello everyone :),i want a favor from you guys...I have just attempted this question on maximum subarray sum(both contiguous and not contiguous)..I have done dp very first time so i would like to have your suggestion..My code give correct output for two testcases.Can you please take a look at my code and tell me where i am going wrong..Many thanks

asked 04 Mar '15, 12:20

doodle90's gravatar image

2★doodle90
96212
accept rate: 7%

edited 04 Mar '15, 12:21


Here is the correct version of the code. http://ideone.com/QFg67S

In the second case, where you have to tell the maximum subsequence, you can choose any element to form the maximum subsequence sum hence we take all positive elements.

The first case ie maximum subarray problem is a standard problem.

Kadane's algorithm(implemented here) solves the problem in O(N). Read up on it if you do not understand the code.

PS : In case of all elements negative, I have assumed the empty subarray to give the maximum sum ie 0 for both cases. Given that the question requires subarray to have atleast one element, in case of the entire array being negative, just print the minimum element.

link

answered 04 Mar '15, 14:08

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

edited 04 Mar '15, 14:09

so my dp part was also wrong ???

(04 Mar '15, 14:21) doodle902★

Yes.

You have initialised dp[1]=a[1]. This assumes that the first element will always be a part of the maximum subsequence sum which will be false if the first element is negative.

Just do the following edit in case of maximum subsequence: dp[1]=max(0,a[1])

(04 Mar '15, 14:35) ironmandhruv4★

What about rest of the things in dp part??Are they all right.,..and Thanks again sir...

(04 Mar '15, 15:01) doodle902★

Sir,i have corrected my code after learning kadane's O(n) but i am still failing in this case(input) correct (output)..can you please check

link

answered 04 Mar '15, 15:16

doodle90's gravatar image

2★doodle90
96212
accept rate: 7%

In case all array elements are negative, just print the minimum element twice.

(04 Mar '15, 15:19) ironmandhruv4★
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:

×2,214

question asked: 04 Mar '15, 12:20

question was seen: 5,460 times

last updated: 04 Mar '15, 15:19