Republic Of Coders- Plus Minus game

help
1

I didn’t get why i got 70 points for this solution. What was i missing if you could tell please?
Question
Solution

2

Well my intution was a Kadane’s Algo, with some minor changes.
Your approach seems to be similar but there are some conditions you should work with :slight_smile:
I am adding my snippet here , hope it works :slight_smile:

void solve7()
{

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;

        vector<int> dp = {0};

        for (auto ele : s)
        {

            if (ele == '-')
            {
                int next = dp.back() - 1;
                if (next < dp.back())
                {
                    dp.push_back(0);
                }
                else
                {
                    dp.push_back(next);
                }
            }
            else
            {
                int next = dp.back() + 1;
                if (next < dp.back())
                {
                    dp.push_back(0);
                }
                else
                {
                    dp.push_back(next);
                }
            }
        }

        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}
1 Like
3

It was mentioned that you have the option not to choose any subarray, so the ans will be >=0for all strings. just put ans=max(0,max_so_far). :slightly_smiling_face:

1 Like
4

No need to any change it’s same as maximum subarray sum
Assume ‘+’ as 1 ans ‘-’ as -1

#include<bits/stdc++.h>
using namespace std;
void test_case(){
	int n; cin>>n;
	string s; cin>>s;
	int res = 0,sum=0;
	for(int i=0; i<n; i++){
		sum+=s[i]=='+'?1:-1;
		res = max(res,sum);
		if(sum<0){
			sum = 0;
		}
	}
	if(res<0)
		cout<<0<<endl;
	else{
		cout<<res<<endl;
	}
}
int main(){
   int t; cin>>t;
   while(t--){
   	test_case();
   }
   return 0;
}
1 Like
6

Ohh now i get it…My solution would also give negative value as the max. for any particular case but it had to be 0 in that case…Thanks

7

Yeah, your solution will give negative value for the cases “-------…”, Happy Coding :grinning:

1 Like