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
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…
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;
}
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()
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…
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
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.
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…