Maximum subarray sum

#1

https://hack.codingblocks.com/contests/c/509/1259

https://ide.codingblocks.com/#/s/28520

problem: showing run error on submitting but works fine when i run it

#2

https://ide.codingblocks.com/#/s/28536

I have commented the problem.
Now it is showing time-limit-exceed and not runtime error.
You solved this in O(N^2). Try a O(N) approach using Kadane’s Algorithm.

1 Like
#3

https://ide.codingblocks.com/#/s/31031
now i hv done it by kadane’s algorithm,and is still showing runerror

#4

https://ide.codingblocks.com/#/s/31052

I have corrected the code and commented the mistake. Array size was small.

1 Like
#5

my code
https://ide.codingblocks.com/s/42997
question link
https://online.codingblocks.com/player/11915/content/5290?s=1502
why it is not showing reqd output

#6

Hey, your code is not correct as you are supposed to take array as input and calculate its max sum for each test case. You should calculate maxsum for one testcase array and then take the input for next test case. I have made the required changes in your code, you can refer this.

#8

CODE

#9

//showing TLE

#include
#include
#include
#define endl “\n”
#define maximum 1000
using namespace std;

//maximum circular sum

int kadane(int a[], int n) {

int currentSum = 0, maxSum = 0;
for (int i = 0; i < n; i++) {
    currentSum += a[i];
    a[i] = -a[i];
    if (currentSum < 0)
        currentSum = 0;
}
maxSum = max(currentSum, maxSum);

return maxSum;

}

int circularSum(int a[], int n, int wrapSum) {

int max_kadane = kadane(a, n);
wrapSum = wrapSum + kadane(a, n);

return (wrapSum > max_kadane) ? wrapSum : max_kadane;

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int tc;
cin >> tc;
while (tc > 0) {
    int n, a[maximum], wrapSum = 0;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        wrapSum = wrapSum + a[i];
    }
    cout << circularSum(a, n, wrapSum);
}

return 0;

}