You are not logged in. Please login at www.codechef.com to post your questions!

×

Subsequence of an array(all elements are positive) with non consecutive elements to give maximum sum.

StackOverFlow Question for Maximum Sum
I am required to find the Subsequence too, but couldn't come up with a solution with O(n) time, just like for Subsequence maximum sum, since my solution involves arrays swapping.
Someone plz suggest some efficient way.
My code:

def find_max_sum(arr):
    incl = arr[0]
    excl = 0
    inc=[0]
    exc=[]
    for i in range(1,len(arr)):
        if excl>incl:
            new_excl=excl
            inc=exc+[i]
        else:
            new_excl=incl
            temp=inc+[]
            inc=exc+[i]
            exc=temp

        incl = excl + arr[i]
        excl = new_excl
    if excl>incl:
        return exc
    else:
        return inc

asked 12 May '18, 23:52

ashubaplawat's gravatar image

2★ashubaplawat
665
accept rate: 11%

edited 13 May '18, 13:24

What do you mean by 'array swapping'?

(13 May '18, 00:11) nilesh31055★

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

(13 May '18, 13:28) ashubaplawat2★

The first ans in the link u mentioned is O(n)

(13 May '18, 22:31) vivek_19982996★

Yeah, but it is returning only the maximum sum value, i wanted to get the Subsequence too in O(n), if it's possible.

(14 May '18, 14:15) ashubaplawat2★

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.

(14 May '18, 17:32) mohit_yadav3892★

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

(14 May '18, 17:45) l_returns5★
showing 5 of 6 show all

Probably this question is posted to solve Changing the Signs. BtW the link you posted seems to have the wrong answer as the most voted one(Consider 4 1 1 5 1).

So, Here's my approach.

Well DP is the answer but its little bit tricky.

Consider a[0,1,2....n]. Suppose $a_i$ is in the subsequence, what can be the first element preceding it (just previous to it in the subsequence).

. $a_{i-1}$ cannot be present.

. $a_{i-2}$ can be .

. $a_{i-3}$ yes it also can be {that's the tricky part}, suppose you are given 4,1,1,5,1. Maximum subsequence sum is 4 + 5.

. Now, what about $a_{i-4}$ . No, it can't be and neither any other number preceding it because if for example, it's the number just previous to $a_i$ in the subsequence, then $a_{i-2}$ will also be present for maximum sum, therefore,$a_{i-2}$ must be the previous element to $a_i$ hence the contradiction.

. Now we can build our simple DP solution by using an array DP which stores max sum ending at index i as $$DP[i] = max(DP[i-1],DP[i-2] + a[i], DP[i-3] + a[i])$$

now just find idx k such that DP[i] is maximum. NOw to find the subsequence use this code

for i=k ; i>=0 ://don't decrement

if(DP[i] == DP[i-1]) i--;

else if(DP[i] == DP[i-2] + a[i] ) i-=2; // store the element;

else i-=3; // store the element.
link

answered 14 May '18, 17:15

pshishod2645's gravatar image

4★pshishod2645
825112
accept rate: 13%

edited 14 May '18, 17:16

Can you explain a bit more. How " DP[i-3] + a[i]" is a separate case?

(14 May '18, 17:27) mohit_yadav3892★

Consider this case :

a[] = {4,1,1,5} // 0 indexed

suppose you are finding DP[3], it is DP[3-3] + a[3] = 4 + 5

But suppose array is a[] = {4,1,1,1,5} // 0 indexed

Then now to find the subsequence ending at 5(index 4), what are the choices for it's previous element (just previous to it), index 2 , 1 are possibilities but let consider index 0 (i.e 4), it can't be the previous element because for suppose it is , then index 2 (i,e 1 )will also be part of subsequence sum to give the maximum sum . hence previous element to 5 can't be 4 but 1.

(14 May '18, 17:39) pshishod26454★

Yeah, i wanted to point the same thing out but didn't have enough reputation points to comment there.
Thanks for your reply though. Really appreciate that.

(15 May '18, 22:48) ashubaplawat2★

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)

static class Node {
    int data;
    Node parent;
    Node(int data, Node parent) {
        this.data = data;
        this.parent = parent;
    }
}

`

//without adjacent elements being included . required answer being {0, 3}
//here the list is a sequence such as {4, 3, 3, 4} for which you want the indices of highest answer

static List<Integer> getIndices(List<Long> list) {
        Node includeIndices = new Node(0, null);
        Node excludeIndices = null;
        Node tempIndex;

        long incl = list.get(0);
        long excl = 0;
        long temp;

        //start from element at index = 1 //0 based indexing
        for (int i = 1; i < list.size(); i++) {
            if (incl > excl) {
                /* current max excluding i */
                temp = incl;
                tempIndex = includeIndices;

                /* current max including i */
                includeIndices = new Node(i, excludeIndices);

                excludeIndices = tempIndex;

                incl = excl + list.get(i);
                excl = temp;
            } else {
                /* current max excluding i */
                //no change required here

                /* current max including i */
                includeIndices = new Node(i, excludeIndices);
                incl = excl + list.get(i);
            }
        }

        Node ansNode = (incl > excl) ? includeIndices : excludeIndices;

        //print return path
        List<Integer> ans = new ArrayList<>();
        while (ansNode != null) {
            ans.add(ansNode.data);
            ansNode = ansNode.parent;
        }

        return ans;
    }

You can check my solution here https://www.codechef.com/viewplaintext/18553477 (JAVA)

link

answered 14 May '18, 15:23

kukreja_vlk's gravatar image

3★kukreja_vlk
603
accept rate: 25%

edited 15 May '18, 11:00

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) kukreja_vlk3★

Was so close... anyways Thanks.

(14 May '18, 16:46) ashubaplawat2★

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.

dp[0]=0
dp[1]=a[1]
st.push(1)
for i=2 to n do
 if dp[i-2]+a[i] greater than dp[i-1] do
   dp[i]=dp[i-2]+a[i]
   st.push(i)
 else do
   dp[i]=dp[i-1]

ans.push(st.top())
prv=st.top()
st.pop()

while !st.empty() do
 if prv-st.top() greater than 1 do
  ans.push(st.top())
  prv=st.top()
 st.pop()

Now ans contains the desired sequence

link
This answer is marked "community wiki".

answered 14 May '18, 15:38

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

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

link

answered 14 May '18, 15:49

l_returns's gravatar image

5★l_returns
1.4k19
accept rate: 25%

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) l_returns5★

where 'i' is same as 'i' in ur code...

(14 May '18, 15:52) l_returns5★

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

link

answered 14 May '18, 16:45

nik_84's gravatar image

5★nik_84
537
accept rate: 0%

edited 14 May '18, 16:47

Can u explain in more detail, @nik_84 ?

(14 May '18, 17:01) vivek_shah985★

@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) nik_845★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×847
×79

question asked: 12 May '18, 23:52

question was seen: 693 times

last updated: 15 May '18, 22:48