最大およびサブ配列2
1504 ワード
整数配列を指定し、重複しない2つのサブ配列を見つけて、それらの和を最大にします.各サブ配列の数値は、配列内の位置が連続しているはずです.最大の和を返します.
注意事項
サブ配列には最低1つの数が含まれます
実際の面接でこの問題に遭遇したことがありますか?
Yes
サンプル
配列
に挑戦
要求時間複雑度O(n)
ポイント:左から右と右から左
注意事項
サブ配列には最低1つの数が含まれます
実際の面接でこの問題に遭遇したことがありますか?
Yes
サンプル
配列
[1, 3, -1, 2, -1, 2]
の2つのサブ配列は、それぞれ[1, 3]
および[2, -1, 2]
または[1, 3, -1, 2]
および[2]
であり、それらの最大および平均は7
である.に挑戦
要求時間複雑度O(n)
ポイント:左から右と右から左
class Solution {
public:
/*
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
int maxTwoSubArrays(vector &nums) {
// write your code here
if (nums.size() == 0) {
return 0;
}
int cur_sum = 0;
int max_sum = nums[0];
vector left(nums.size(), 0);
vector right(nums.size(), 0);
for (int i = 0; i < nums.size(); i++) {
cur_sum = max(cur_sum + nums[i], nums[i]);
max_sum = max(cur_sum, max_sum);
left[i] = max_sum;
}
cur_sum = 0;
max_sum = nums[nums.size() - 1];
for (int j = nums.size() - 1; j >= 0; j--) {
cur_sum = max(cur_sum + nums[j], nums[j]);
max_sum = max(cur_sum, max_sum);
right[j] = max_sum;
}
max_sum = INT_MIN;
for (int k = 0; k < nums.size() - 1; k++) {
max_sum = max(max_sum, left[k] + right[k + 1]);
}
return max_sum;
}
};