Approach to a problem | C++

Question

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

Answer 1

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

Answer 2

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

Answer 3

Ketan Lalcheta

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

Answer 4

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 ...

Answer 5

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? 😉

Answer 6

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

Answer 7

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

Answer 8

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!

Answer 9

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 ?

Answer 10

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?

Answer 11

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 🤔

Answer 12

Ketan Lalcheta here the result of my Lunch break
(w/o knowledge of c++)

https://code.sololearn.com/cAh53r8JMpuq/?ref=app

Answer 13

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

Answer 14

This looks great..... Perfect it seems

Worked for this input as well

int a [5] = {4, 7 , 1, 9, 18};

Answer 15

Thanks Gaurav Agrawal ... Description is awesome 👌👍

Answer 16

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

Answer 17

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

Answer 18

Coding Cat [sleeps on Java] unfortunately no I guess

Its like we can't decide steps and j variable's initial condition

Answer 19

Ketan Lalcheta what is time complexity of NlogN? Like, gimme an example plz

Answer 20

Rishi plz go through this...

https://www.sololearn.com/learn/6362/?ref=app

Feel free to ask for questions