×

# 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 2★doodle90 96●2●12 accept rate: 7%

 1 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. answered 04 Mar '15, 14:08 333●2●3●9 accept rate: 20% 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) What about rest of the things in dp part??Are they all right.,..and Thanks again sir... (04 Mar '15, 15:01) doodle902★
 0 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 answered 04 Mar '15, 15:16 2★doodle90 96●2●12 accept rate: 7% In case all array elements are negative, just print the minimum element twice. (04 Mar '15, 15:19)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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