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
Problem: Maximum Subarray Sum
Problem Link:
Companies Asked: Cerner Corporation, Amazon, Microsoft, Goldman Sachs, Facebook, Cloudera
Approach:
Take a variable sum to calculate the running sum while accessing the array.
Take another variable maxSum that contains the maximum sum of a subarray.
Initiate maxSum = 0 ( INT_MIN only for the 2nd question ).
Start traversing the array.
Add each element to the sum.
Update maxSum if the sum becomes greater than maxSum.
Reset sum = 0, if the sum becomes less than 0.
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;
}