36. Maximum Subarray(难)
08 Jul 2020 | Daily Algorithms
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
else if (nums.size() == 1) return nums.at(0);
int int_local_max = nums.at(0);
int int_global_max = nums.at(0);
int sz_length = nums.size();
for (int i = 1; i < sz_length; i++) {
int_local_max = max(int_local_max + nums.at(i), nums.at(i));
int_global_max = max(int_local_max, int_global_max);
}
return int_global_max;
}
};
-
Apparently, this is an optimization problem, so DP is the one for choice.
-
When we are talking about DP, the first problem comes out to our mind should be: what’s the statement of the sub-problem, whose format should satisfy that if we’ve solved a sub-problem, it would be helpful for solving the next-step sub-problem, and, thus, eventually helpful for solving the original problem.
-
Here is the sub-problem we state: denote int_local_max[i] as the max-sub-array-sum that ends with nums[i]. The relationship between the two steps is simple: int_local_max[i + 1] = max (int_local_max[i] + nums[i + 1], nums[i + 1]) or int_local_max[i + 1] = (int_local_max[i] > 0) ? int_local_max[i] + nums[i + 1] : nums[i + 1].
-
Now, all we have to do is to scan through the array, and find which int_local_max[i] is the maximum of all the int_local_maxs.
-
In the OP’s code, ans works like int_global_max, and
sum=max(sum,0); // prev step
sum+=A[i];
- works like int_local_max = max(int_local_max + nums.at(i), nums.at(i));. Hence, basically, the code uses DP(Dynamic Programming) algorithm, and sum in the code contains the sub-problem idea.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
else if (nums.size() == 1) return nums.at(0);
int int_local_max = nums.at(0);
int int_global_max = nums.at(0);
int sz_length = nums.size();
for (int i = 1; i < sz_length; i++) {
int_local_max = max(int_local_max + nums.at(i), nums.at(i));
int_global_max = max(int_local_max, int_global_max);
}
return int_global_max;
}
};
-
Apparently, this is an optimization problem, so DP is the one for choice.
-
When we are talking about DP, the first problem comes out to our mind should be: what’s the statement of the sub-problem, whose format should satisfy that if we’ve solved a sub-problem, it would be helpful for solving the next-step sub-problem, and, thus, eventually helpful for solving the original problem.
-
Here is the sub-problem we state: denote int_local_max[i] as the max-sub-array-sum that ends with nums[i]. The relationship between the two steps is simple: int_local_max[i + 1] = max (int_local_max[i] + nums[i + 1], nums[i + 1]) or int_local_max[i + 1] = (int_local_max[i] > 0) ? int_local_max[i] + nums[i + 1] : nums[i + 1].
-
Now, all we have to do is to scan through the array, and find which int_local_max[i] is the maximum of all the int_local_maxs.
-
In the OP’s code, ans works like int_global_max, and
sum=max(sum,0); // prev step
sum+=A[i];
- works like int_local_max = max(int_local_max + nums.at(i), nums.at(i));. Hence, basically, the code uses DP(Dynamic Programming) algorithm, and sum in the code contains the sub-problem idea.
Comments