Engineer bro!
Fri Oct 08 2021 (2 years ago)
Engineer by mistake!
I am a software engineer by passion
You are given an array and you have to find a continues sub-array of which has the largest sum over any other sub-array of .
1 <= N <= 1e6
-1000 <= A[i] <= 1000
The first and only input of the algorithm is an array .
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:
Output 2:
Explanation 1: The subarray has the maximum possible sum of 10.
Explanation 2: The subarray has the maximum possible sum of .
int maxSubArray(const vector<int> &A) {
// return max sum
}
The brute force way is to go through each sub-array of then calculate its sum and compare it with the sum of the other subarrays of . 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 -
Space -
is size of array
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 , 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 as starting point of a sub-array. Then add an element each time to get a sub-array of size greater than than the previous sub-array.
For example, I have sub-array . To get the next sub-array, just append to it. Now, the next sub-array will looks like, .
So, instead of iterating over again, we can just use sub-array to get the sum of by just adding to .
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