Approach to a problem | C++ | Sololearn: Learn to code for FREE!

+2

Approach to a problem | C++

Hi I don't expect any available code for me... Can anyone just guide on how to approach below problem ? Thanks in advance...! //find maximum sum from input array / vector... you can skip anything in between but at least two subsequent elements cannot be picked // for example, // 1 9 2 4 11 : 20 is output // 1 9 11 4 : 13 is output // 2 3 8 : 10 is output

9/15/2021 8:42:46 PM

Ketan Lalcheta

26 Answers

New Answer

+3

Ketan Lalcheta This one? This is not from me. I have now to use pencil and paper to find out what's going on here https://code.sololearn.com/c7Wyp6oHTE2W/?ref=app

+4

Idea: dp1[i] --> max possible sum you can generate from index 0 to i, such that you have included ith element. dp2[i] --> max possible sum you can generate from index 0 to i, such that you are not including ith element dp1[i] = a[i]+max(dp1[i-2], dp2[i-1]) dp2[i] = max(dp1[i-1], dp2[i-1]) ans will be max(dp1[n-1], dp2[n-1]) I verified it with all your test cases. It is variation of a standard dp problem house robber. Time Complexity: O(n) Space Complexity: O(n) //can be reduced to O(1) Edit: I think its the same problem can be done with single dp array. dp[i] --> max sum we can generate from a[0...i] dp[i] = max(dp[i-1], a[i]+dp[i-2]); //not take ith element or take it

+2

Ketan Lalcheta Well, we must choose some of them which has the greatest summation right?

+2

Just sort the array. The two largest numbers will provide the largest sum. The C standard library has a sorting function qsort(). http://www.cplusplus.com/reference/cstdlib/qsort/ and C++ has std::sort(). http://www.cplusplus.com/reference/algorithm/sort/ Edit: OOPS! I missed the bit about consecutive numbers. Sorry.

+2

Maybe find the largest element first and take note of its index. Then find second largest element whose index is not nearby. Lastly sum the two ...

+2

Pseudo Code: a = array[....] len = length of array maxSum = a[0] for i = 0 to i < len-2 step 1 for j = i+2 to j < len step 1 if a[i] + a[j] > maxSum maxSum = a[i] + a[j] print maxSum I think that's nice, isn't it? 😉

+2

Uhh, sorry for that. I misunderstood it. Now it's a completely different Problem 😂

+2

Compared algorithm proposed by Coding Cat [mouse break] to a brute force algorithm just for fun and because the algorithm is not much intuitive (at least for me). https://code.sololearn.com/cqiFi7X0pXs2/?ref=app

+1

Define an array to collect all given integers. After that, skip between ones in the array. Like if you take the first element of the array, you can't take second element. But you can take third one... etc. You can use a loop for scanning all elements and a condition for controlling the close elements. I hope, it helps. Happy coding!

+1

Yeah that's cool 👌 but time complexity would be N*logN...To store the index in this caee, I believe we will need extra space of O(N) . Is this the best possible solution or something else is also possible ?

+1

Oh, that's bad. But I don't got you. We can't use for-loop? Or it's not possible to get the value from i from the outer loop to the inner loop? Is this an c++ specific behavior?

+1

Here a c++ loop with step = 1 for (int i = 0; i < 5; i++) { cout << i << "\n"; } And instead the number 5 set in the Array-lenght - 2 Next loop for (int j = i+2; j < len; j++) { ... } Idk why this should not work 🤔

+1

Ketan Lalcheta here the result of my Lunch break (w/o knowledge of c++) https://code.sololearn.com/cAh53r8JMpuq/?ref=app

+1

Thanks for your effort and time Coding Cat [sleeps on Java] and sorry if I could not make question clear int arr [5] = {14, 17 , 15, 11, 8}; output generated by code is 29 but expected output is 37.. 14+15+8 as neither of them are subsequent

+1

This looks great..... Perfect it seems Worked for this input as well int a [5] = {4, 7 , 1, 9, 18};

+1

Thanks Gaurav Agrawal ... Description is awesome 👌👍

0

Thanks for response mesarthim but it won't work simply by skipping just close elements... In first set of input , index 1 and 4 has been considered not like 1 and 3. How to choose elements is main issue to maximize the output sum

0

This question lacks proper description. Case 1 is understandable but you have to explain how the answer ends up being 13 and 8 for other cases respectively otherwise, finding the solution on here would take you forever

0

Runtime Terror[ Busy ] thanks for asking this question... Let me correct answer for last input to 10 instead of 8. Updated in question now as well... For second case , one possible pick is 1+11 and other is 9+4 so 13>12 and hence answer is 13 For last case, answer is 10 as 8+2 is more than 3 alone

0

Coding Cat [sleeps on Java] unfortunately no I guess Its like we can't decide steps and j variable's initial condition