Let look at the first question:
Q1: Given an array with integers, what is the maximum sum of all the possible sub-arrays?
Analysis:
There are (N*(N+1))/2 distinct sub-arrays in total. Thus, if we check each one step by step, the time complexity is O(N^2), which gives an upper-bound of our methods.
Can we do better?
The answer is yes.
The general idea is:
1): get the maximum sum for all the subarrays ending with each element;
2): get the maximum of all the maximum sums obtained in 1).
Imagine we have handled the situation for all the elements to (i-1). Now we need to deal with the ith element.
Let define sum as the maximum sum ending the (i-1), and res is the maximum sum in the range from 0 to (i-1).
Then, we need to update sum to make it ending with the ith element,
sum = max(sum + arr[i], arr[i])
then, we can update the res by choosing the maximum,
res = max(res, sum)
So now the sum is the maximum sum of subarrays ending with the ith element;
res is the maximum sum of subarrays in the range of [0, i].
See the code below:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if(!n) {
cout<<"invalid input!";
return 0;
}
int res = nums[0], sum = nums[0];
for(int i=1; i<n; ++i) {
sum = max(sum + nums[i], nums[i]);
res = max(res, sum);
}
return res;
}
};The above time complexity is O(N), the space complexity is O(1).
Let try a different way: let use sum[i] represents the continuous sum from arr[0] to arr[i]. Then the maximum subarray sum (ending with the ith element) should be:
max(sum[i] - sum[j]) where j>=0 and j< i;
which is equivalent to:
sum[i] - min(sum[j]) where j>=0 and j<i;
Since we have known all the sum[j] before sum[i], thus we can just use one variable minSum to memorize this.
Then the key formula becomes;
minSum = min(minSum, sum[i-1]); // minimum {sum[j]} where j in [0, i-1]
sum [i] = sum[i-1] + arr[i]; // update sum to the current ith element;
maxDiff = sum[i] - minSum; // maximum sum ending with the ith element;
res = max(res, maxDiff); // maximum sum in [0, i]
Since we only need sum[i-1] and sum[i], we can use only one variable sum for this:
minSum = min(minSum, sum); // minimum {sum[j]} where j in [0, i-1]
sum = sum + arr[i]; // update sum to the current ith element;
maxDiff = sum - minSum; // maximum sum ending with the ith element;
res = max(res, maxDiff); // maximum sum in [0, i]
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if(!n) {
cout<<"invalid input!";
return 0;
}
int res = nums[0], sum = nums[0], minSum = min(0, nums[0]);
for(int i=1; i<n; ++i) {
minSum = min(minSum, sum);
sum += nums[i];
res = max(res, sum - minSum);
}
return res;
}
};The time complexity is still O(N), and space complexity is O(1).
Now let look at a follow up:
Q2: What is the maximum sum subarray with the length no smaller than K?
Actually Q1 is a special case of Q2: K = 1.
The idea is the same as the second method for Q1. The only difference is that, we can only update minSum upto the (i-k)th element.
See the code below:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = 0, minSum = 0, n = nums.size();
if(K <= 0 || n < K) {
cout<<"invalid input!";
return 0;
}
vector<int> sum(n, 0);
sum[0] = nums[0];
for(int i=1; i<K; ++i) sum[i] = sum[i-1] + nums[i];
res = sum[K-1];
for(int i=K; i<n; ++i) {
minSum = min(minSum, sum[i-K]);
sum[i] = sum[i-1] + nums[i];
res = max(res, sum[i] - minSum);
}
return res;
}
};The time complexity is O(N), and the space complexity is O(N).
Now let look at another question:
Q3: What is the maximum sum subarray with the length no longer than K?
The idea is still the same, we will maintain a minSum in the range from [i-k+1, i], which can be achieved by the "sliding-window-minimum" method (and the window size is K).
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = 0, minSum = 0, n = nums.size();
if(K <= 0 || n < K) {
cout<<"invalid input!";
return 0;
}
vector<int> sums(n, 0)
res = nums[0], sums[0] = nums[0], minSum = min(0, nums[0]);
List<int> lts; // save the index of sums
lst.push_back(0);
for(int i=1; i<n; ++i) {
sums[i] = sums[i-1] + nums[i];
while(lts.size() && lts.front() + K <= i) lts.pop_front();
while(lts.size() && sums[lts.back()] >= sums[i]) lts.pop_back();
lts.push_back(i);
minSum = min(minSum, sums[lts.front()]);
res = max(res, sum[i] - minSum);
}
return res;
}
};The time complexity is O(N), and the space complexity is O(N).
Okay, let move to another question:
Q4: What is the largest average for all the subarrays of an array with integers?
Analysis:
The subarray giving the largest sum may have a larger length, thus the average may be not be the largest.
Again the brute force way is O(N^2) by going through all the subarrays. But we can do better.
One way to do this is using binary search:
The largest average should in the rang of [min, max] of the array. Then, set mid as
mid = min + (max - min) / 2;
if there is no subarray having a larger or equal average of mid, which mean this mid is too large, then we can set the right = mid;
otherwise, left = mid.
Then the left should be the maximum average of all subarrays.
Then how to know whether there is a subarray having an average larger than the mid in O(N)?
We can modify the continuous sum by minusing the mid for each element. In this way, we do not need to take care of the length of the subarray. (This is the tricky part, think for a minute if not get it).
Similar as previously, we will maintain a minSum, then once we find the current sum > minSum, which mean there is a subarray having average larger than mid.
See the code below:
class Solution {
public:
double findMaxAverage(vector<int>& nums) {
int n = nums.size();
if(!n) {
cout<<"invalid array!"<<end;
return 0;
}
double left = *min_element(nums.begin(), nums.end());
double right = *max_element(nums.begin(), nums.end());
double epslon = 1e-5;
while (right - left > epslon) {
double sum = 0, minSum = 0, mid = left + (right - left) / 2;
bool find = false;
for (int i = 0; i < n; ++i) {
minSum = min(minSum, sum);
sum += nums[i] - mid;
if (sum > minSum) {find = true; break;}
}
if (find) left = mid;
else right = mid;
}
return left;
}
};The time complexity is O(Nlog(max-min)), the space complexity is O(1).
Now let us look at another question:
Q5: What is the largest average for all the subarrays with length no smaller than K of an array with integers?
We can just follow the idea used in the above question, and the only difference is that: we only need to update the minSum to the (i - K)th element.
See the code below:
class Solution {
public:
double findMaxAverage(vector<int>& nums, int K) {
int n = nums.size();
vector<double> sums(n + 1, 0);
double left = *min_element(nums.begin(), nums.end());
double right = *max_element(nums.begin(), nums.end());
while (right - left > 1e-5) {
double minSum = 0, mid = left + (right - left) / 2;
bool find = false;
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1] - mid;
if (i >= k) {
minSum = min(minSum, sums[i - k]);
}
if (i >= k && sums[i] > minSum) {find = true; break;}
}
if (find) left = mid;
else right = mid;
}
return left;
}
};The time complexity is O(Nlog(max-min)), the space complexity is O(N).
At this moment, it is natural to have the next question, which is the last question for this post:
Q6: What is the largest average for all the subarrays with length no longer than K of an array with integers?
If you read through this post, this question should not be difficult to solve. So I decide to leave it to you without giving an answer here.
Thanks for reading, happy coding!
No comments:
Post a Comment