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
1 Like

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.

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)

1 Like

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.

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

1 Like

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…

1 Like

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…

where ‘i’ is same as ‘i’ in ur code…

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

Was so close… anyways Thanks.

Can u explain in more detail, @nik_84 ?

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

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

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.

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.

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…

@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