Great Explanation!
1 Like
Can someone find the bug in this I am not getting what I am missing
Problem was not tough, but why do you write statements so bad? it took me 30 mins to under which subsequence meant which sub sequence and i still don’t how was out put expected.
someone tell me whats wrong in this : CodeChef: Practical coding for everyone
i keep my self free whole day and at the end this is really sad.
5 Likes
(Since nobody helped so) I think you made a mistake you should write in place of
if(sum == 0||count==n){
cout<<0<<endl;
cout<<0<<endl;
}
this
“if(sum == 0||count==n){
cout<<sum<<endl;
cout<<0<<endl;
}”
My solution O(n) time:
think in terms of hoare’s partition algorithm and realise that we can always separate the
numbers greater than 0 than the numbers which are less than zero(just like we used to do
In quick sort)
Hope it helps!!!
1 Like
Try this case:
12
1 1 1 -1 -1 1 -1 1 -1 -1 0 0
Your output:
5
6 4 5 6 8 11 12
Sum is undoubtedly correct but with that sequence it is unachievable.
Reason is while counting pos you didn’t count zeroes but while swapping you are!
My solution is correct.
The final sequence will be:
1 1 1 0 0 1 1 -1 -1 -1 -1 -1 -1
so sum of first 7 elements is 5.
Please cross check once.
How 7th element has turned to 1?
It was -1 in test case i provided and sequence to be reversed according to output from CodeChef: Practical coding for everyone : 4 5 6 8 11 12. Which means, final array: 1 1 1 0 0 1 -1 1 -1 -1 -1 -1.
Brother you are make a mistake while reversing the sequence .
Please check once again.
My solution is correct!.
I’m unable to find the bug can somebody help, what I did was, I collected all positive element index before the last negative indexes which are of the type [+,-,+] here’s my submission.
I used these test case to judge my solution…
there were build one by one as i was continuously getting WA ,
4
5
-4 2 -4 3 -5
3
-3 -2 -1
7
-2 5 -6 2 3 -7 -8
6
0 8 9 -8 8 -9
Hope it helps
keep eye on the 2nd & 4th one
The 0 in the array may be the culprit
2 Likes
for anyone thinking in terms of partition !!
1st
Don’t care about the 0s in the array bcoz of well asuring line
maximum sum of a contiguous subsequence (possibly an empty sequence, with sum 0)
2nd
So we are left with purely +ve and purely -ves..
3rd
start = 0,end=n-1;
while(start<end){
...
}
Now this is two pointers
4th
Inside while loop
increment the start untill you not get a pure -ve
decrement the end untill you not get a pure +ve
swap the purely -ve at start with purely +ves in the end
5th
Now finally see what your array looks like on console
by printing it
6th
Now this is what we want ,,,
Go ahead
smash it!!
The idea behind is to see the problem in terms of application of partition technique…
Strictly speaking we do not need a somewhat ad-hoc approach
Elementary knowledge of the partition will work
So use it…
It has so much to yield evertime…
Got correct ans-
here it is for your test cases-
5
2 2 5
0
0
10
4 2 4 6 7
25
4 2 3 4 6
https://www.codechef.com/viewsolution/38110243
Can anyoe tell the mistake i my soln’
Thanks in advance
I generally notice that if a problem is very easy to code codechef tags it as easy even though the complexity of coming up with the solution is not easy and needs out of the box thinking.