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

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.

Thanks for the video editorial such a nice explanation with correctness

Hey pls tell me what is wrong here

#include

#include

using namespace std;

#define ll long long

int main()

{

ll t;

cin>>t;

while(t–)

{

ll n;

cin>>n;

ll a[n];

ll ans=0;

ll p=0;

vector vekt;

for(ll i=0;i<n;i++)

{

cin>>a[i];

if(a[i]>0)

{

ans+=a[i];

p++;

}

}

if(ans==0|| p==n)

{

cout<<ans<<endl;

cout<<“0”<<endl;

continue;

}

for(ll i=0;i<p;i++)

{

if(a[i]<0)

vekt.push_back(i+1);

}

for(ll i=p;i<n;i++)

{

if(a[i]>=0)

vekt.push_back(i+1);

}

cout<<ans<<endl;

cout<<p<<" “;

for(auto go:vekt)

{

cout<<go<<” ";

}

cout<<endl;

}

}

https://www.codechef.com/viewsolution/38135024

The solution is based on the following understanding:

Suppose I have numbers -1 1 2 -3 -4 4 -5

Then I look up for the first sequence of negative numbers after a positive number is encountered. (In this case -3, -4). The index of the negative numbers are stored till I encounter a positive number.

Then in future all positive number indexes are stored (in this case index 6 for number 4).

Finally I have indexes 4 5 6 on the above case which is correctly reversing for the problem statement.

I took care of all corner cases as far as I am aware. However I am unable to find any error. I ran my code on countless test cases.

Can anyone help me?

I’m getting TLE for this code.

Is it because I used Stream API?

void main() throws IOException {

int T = in.ri();

while (T-- > 0) {

int N = in.ri();

ArrayList a = in.riaa(N);

int P = 0;

for (Integer integer : a) {

if (integer > 0) P++;

}

ArrayList toBeRev = new ArrayList<>();

for (int i = 0; i < P; i++) {

if (a.get(i) < 0) {

toBeRev.add(i + 1);

}

}

//out.prln(toBeRev);

for (int i = P + 1; i < a.size(); i++) {

if (a.get(i) > 0) {

toBeRev.add(i + 1);

}

}

a.sort(Comparator.reverseOrder());

int sum = a.stream().filter(x -> x > 0).mapToInt(x -> x).sum();

System.out.println(sum);

if (toBeRev.size() > 0) {

toBeRev.forEach(x -> System.out.print(x + " "));

System.out.println();

} else {

System.out.println(0);

}

}

}

Why do we need to create a separate index list for negative numbers. The required sum that is the maximum sum is formed by the positive numbers only . Hence we can print only the positive numbers in the array. Why do we need negative numbers to be printed as well?