給定整數陣列，找出其中一些連續元素的最大可能和。
Example For inputArray = [2, 3, 5, 1, 6]k = 2，輸出應該是 solution(inputArray, k) = 8。
所以我的程式是有效的，至少在我見過的測驗用例中是有效的，除了它跳過了第一個元素。
可能有多種解決方法。通過將第一個元素的副本插入到陣列中，或者創建一個單獨的回圈來回圈第一次檢查 (2 3 = 5)。但這些解決方案似乎都不夠優雅。我想以最好的方式解決這個問題，但我似乎找不到一個好的解決方案。這是我的代碼：
vector<int> arr = {1, 3, 4, 2, 4, 19, 1};
int sum {};
int max {};
int k = 3;
for (int i {}; i < arr.size(); i)
{
sum = 0;
int x = k;
for (int j = i 1; j < arr.size(); j)
{
sum = arr.at(j);
--x;
if (x == 0)
{
cout << sum << endl;
break;
}
}
if (sum > max)
{
max = sum;
}
}
cout << max << endl;
如您所見，我的內部 for 回圈從索引開始，j 1因此默認情況下它會跳過向量中的第一個索引。我該如何解決？有沒有我可以做的 if 陳述句來操縱回圈只有j = i 1 if i != 0?
uj5u.com熱心網友回復：
我可以做一個 if 陳述句來操縱回圈
j = i 1 if i != 0嗎？
您可以使用三元運算子來執行此操作，如下所示：
int j = i != 0 ? i 1 : i;
三元運算子的結構：
但是，我很好奇：為什么你不將值添加i到總和（所以它總是總和的一部分），而不是從零開始？
sum = array[i];
uj5u.com熱心網友回復：
可能有多種解決方法。[...] 我想以最好的方式解決這個問題。
然后，考慮一個 O(N) 演算法，而不是 O(N^2) 一個：
#include <iostream>
#include <vector>
auto max_sum_of_k(std::vector<int> const& v, size_t k)
{
// Sum the first k elements.
long long current_sum{};
size_t i{};
for ( ; i < k and i < v.size(); i )
{
current_sum = v[i];
}
// Update the running sum, without a nested loop.
long long sum{ current_sum };
for ( ; i < v.size(); i )
{
current_sum -= v[i - k];
current_sum = v[i];
if ( sum < current_sum )
sum = current_sum;
}
return sum;
}
int main()
{
std::vector<int> arr = {1, 3, 4, 2, 4, 19, 1};
for (size_t k{}; k <= arr.size(); k)
{
std::cout << "k: " << k << " max sum: " << max_sum_of_k(arr, k) << '\n';
}
}
uj5u.com熱心網友回復：
首先請注意，只有在k不超過陣列長度的情況下才能執行此任務。
現在一個有效的解決方案是
計算前 k 個元素的總和，然后
反復從總和中洗掉第一個元素并添加下一個元素。這可以節省大量資金。
int j;
int Sum= A[0];
for (j= 1; j < k; j )
Sum = A[j];
// Here we have the first sum
for ( ; j < length; j )
{
Sum-= A[j - k];
Sum = A[j];
// Here we have the next sums
}
我把你留作練習，以保持最大金額。
請注意，不建議對浮點型別使用求和更新技巧，因為會累積數值誤差。
uj5u.com熱心網友回復：
使用模板有點花哨的方法：
template <typename In>
auto sum_at_most_n(In b, In e, size_t n) {
typename std::iterator_traits<In>::value_type sum{};
while (b != e && n--) {
sum = sum *b ;
}
return std::pair{sum, b};
}
template <typename In>
auto max_sum_of_k(In b, In e, size_t k) {
auto [sum, head] = sum_at_most_n(b, e, k);
auto max_sum = sum;
while (head != e) {
sum = sum - *b *head ;
max_sum = std::max(max_sum, sum);
}
return max_sum;
}
template <typename Container>
auto max_sum_of_k(Container c, size_t k) ->
typename std::iterator_traits<decltype(std::begin(c))>::value_type {
return max_sum_of_k(std::begin(c), std::end(c), k);
}
只是迭代元素，然后減去不再是總和一部分的元素，
但我真的建議學習如何撰寫測驗。請參閱演示鏈接：
演示
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/430118.html
標籤：C