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
Here is the correct version of the code. QFg67S - Online C++ Compiler & Debugging Tool - Ideone.com
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.
1 Like
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
so my dp part was also wrong ???
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])
What about rest of the things in dp part??Are they all right.,…and Thanks again sir…
In case all array elements are negative, just print the minimum element twice.