Engineer bro!
Fri Oct 08 2021 (1 year ago)
Engineer by mistake!
I am a software engineer by passion
You are given an array $A$ and you have to find a continues sub-array of $A$ which has the largest sum over any other sub-array of $A$.
1 <= N <= 1e6
-1000 <= A[i] <= 1000
The first and only input of the algorithm is an array $A$.
Return an integer representing the maximum possible sum of the contiguous subarray.
Input 1:
A = [1, 2, 3, 4, -10]
Input 2:
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output 1:
$10$
Output 2:
$6$
Explanation 1: The subarray $[1, 2, 3, 4]$ has the maximum possible sum of 10.
Explanation 2: The subarray $[4,-1,2,1]$ has the maximum possible sum of $6$.
int maxSubArray(const vector<int> &A) {
// return max sum
}
The brute force way is to go through each sub-array of $A$ then calculate its sum and compare it with the sum of the other subarrays of $A$. Keep the maximum sum overall.
int maxSubArray(const vector<int> &A) {
// initially initialize maximum as minimum
int maxSum = INT_MIN;
for(int i=0; i<A.size(); i++){
for(int j=i; j<A.size(); j++){
// for every sub array calculate the sub array sum
// them compare it with maxSum and update maxSum as maximum of maxSum and curSum
int curSum = 0;
for(int k=i; k<= j; k++){
curSum += A[k];
}
// update maxSum
maxSum=max(maxSum,curSum);
}
}
return maxSum;
}
Time - $O(n)$
Space - $O(1)$
$n$ is size of array $A$
Before understanding that how to optimize the code, I would like to explain to you that how we are processing the sub-arrays.
Consider the array $[1,2,3]$, if we print all the sub-arrays using the above code, then it'll be printed as follows.
1
1, 2
1, 2, 3
2
2, 3
3
You can see that the first loop is considering every index of $A$ as starting point of a sub-array. Then add an element each time to get a sub-array of size greater than $1$ than the previous sub-array.
For example, I have sub-array $[1]$ $(A[0])$. To get the next sub-array, just append $A[1]$ to it. Now, the next sub-array will looks like, $[1,2]$.
So, instead of iterating over $[1,2]$ again, we can just use sub-array $[1]$ to get the sum of $[1,2]$ by just adding $2$ to $sum([1])$.
This way we can eliminate the third loop and calculate the sum of the sub-array on the fly.
int maxSubArray(const vector<int> &A) {
// initially initialize maximum as minimum
int maxSum = INT_MIN;
for(int i=0; i<A.size(); i++){
int subArraySum = 0;
for(int j=i; j<A.size(); j++){
subArraySum += A[j];
maxSum = max(maxSum,subArraySum);
}
}
return maxSum;
}
Ā© 2021 dsabyte. All rights reserved