hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Maximum Subarray Sum


  • Approach:

    1. Take a variable sum to calculate the running sum while accessing the array.

    2. Take another variable maxSum that contains the maximum sum of a subarray.

    3. Initiate maxSum = 0 ( INT_MIN only for the 2nd question ).

    4. Start traversing the array.

    5. Add each element to the sum.

    6. Update maxSum if the sum becomes greater than maxSum.

    7. Reset sum = 0, if the sum becomes less than 0.

    8. Return maxSum.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1)


Code [C++]

#include<bits/stdc++.h>

using namespace std;

int main() {

int N;

cin>>N;

vector<int>arr(N);

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

cin>>arr[i];

}

int sum = 0, maxSum = 0;

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

sum += arr[i];

if(maxSum < sum){

maxSum = sum;

}

if(sum < 0){

sum = 0;

}

}

cout<<maxSum<<endl;

}