StackOverFlow Question for Maximum Sum
asked 12 May '18, 23:52
showing 5 of 6
show all

Yes it is possible with the help of LinkedList which I applied for solving MAY18 question CHSIGN. The problem I believe is in memory allocation in the else statement for all values in the exclude set which causes the approach to be O(n^2). Here is my java solution (quite similar to yours) that uses a linkedlist to keep a track of only the current element's parent. This way I was able to save copying of old items in every loop iteration > The following is the Node structure (Remember we are not using arrays)
You can check my solution here https://www.codechef.com/viewplaintext/18553477 (JAVA) answered 14 May '18, 15:23
Ignore the size allocation in one of the last few lines..that was something specific to my code and at this time I am unable to edit it out.
(14 May '18, 15:33)
Was so close... anyways Thanks.
(14 May '18, 16:46)

I used a stack to store the indices of elements which increase the sum. Once the iteration is done pop the indices from top of stack one by one... Very first element will always be part of sequence and later check if the next index has difference greater then 1 with last selected index for sequence.
Now ans contains the desired sequence
link
This answer is marked "community wiki".
answered 14 May '18, 15:38

You can do this question with current time limit by array swapping and array copying.... (boolean array) I did it.. have a look at my solution.. It ran in 0.33 secs https://www.codechef.com/viewsolution/18560397 magical DP loop is the edited version of the code u provided... answered 14 May '18, 15:49
i guess it's not O(n) though cuz it takes O(i) iterations again if 4 6 6 4 type condition arises.. where we have to take 6+6 and skip 4+4....
(14 May '18, 15:52)
where 'i' is same as 'i' in ur code...
(14 May '18, 15:52)

You can simply traverse the dp array and get the required sequence or you can use DSU as well. Link to solution by traversing dp array: https://www.codechef.com/viewsolution/18479203 answered 14 May '18, 16:45
Can u explain in more detail, @nik_84 ?
(14 May '18, 17:01)
@vivek_shah98 if you are at index i of dp array , this element , dp[i]= dp[i+1]; or dp[i]=ar[i]+dp[i+2]; if case 1, continue; else add ar[i] to answer
(14 May '18, 19:17)

What do you mean by 'array swapping'?
I have included the code, it is not in O(n), i suppose because of the exchanging the elements of these 2 arrays. Please suggest some other way to do this...
The first ans in the link u mentioned is O(n)
Yeah, but it is returning only the maximum sum value, i wanted to get the Subsequence too in O(n), if it's possible.
In C++, You can use vector for arrays and then you can swap them in O(1) time using swap function provided in STL. Swapping arrays just means changing the name of array their internal representation will always be same. In C, You can use the pointers to arrays and then you just swap the pointers to swap the array. Here also you are changing the name only.
But it needs copying an array also which needs O(n) time.. @mohit_yadav389 And swapping an array also takes O(1)(no need of using vector).. use pointer and malloc... see my answer for solution link.. i have swapped and copied an array....