Max circular sum

#1

one test case is not passing

#2

consider all these cases for answers

if(a[n-1]>0)
		{
			i=0;
		}

if a[n-1] is less than zero, then i is set to zero.
it will run in an infinite loop.

Correct Approach :

image
image847×443 57.8 KB

first case can be calculated by Kadane.
for second ques, if you multiply the array by -1 and then do kadane it will give min subarray.

#3

Only one of the test case is not passing in my code please tell the mistake in that…

#4

you are making code more and more complex.
why are you using flag(No need)

you have to only choose between two answers, one from kadane and the other by adding kadane(after inverting) to total;

see this code for better understanding

#include<bits/stdc++.h>
#define moduli 998244353
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define um unordered_map

using namespace std;

int kadane(vector<int> a) {
    vector<int> dp(a.size());
    dp[0] = a[0];
    int maximum = -INT_MAX;

    for (int i = 1; i < a.size(); ++i)
    {
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        maximum = max(maximum, dp[i]);
    }

    return maximum;
}

void solve(int tc) {
    int i, j, k, n, m, ans = 0, cnt = 0, sum = 0;
    vector<int> a;
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;
        a.pb(temp);
    }

    if (n == 1) {
        cout << a[0] << endl;
        return;
    }

    int max_positive = kadane(a);

    int total = 0;

    for (int i = 0; i < n; ++i)
    {
        total += a[i];
        a[i] = -1 * a[i];
    }

    int max_negative = kadane(a);
    int after_removing_negative = total + max_negative;

    if (max_positive >= after_removing_negative or after_removing_negative==0) {
        cout << max_positive << endl;
    }
    else {
        cout << after_removing_negative << endl;
    }

}


int32_t main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif

    ios_base:: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    int t; cin >> t; while (t--)
    {
        solve(tc);
        tc++;
    }
}
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.