-2

私がこれまでに行ったこと：

Kadane のアルゴリズムを使用して合計を見つけました。

条件が満たされたときに要素を格納するベクトル「res」を作成しました。

問題: たとえば、入力が配列の場合: {-2, -3, 4, -1, -2, 1, 5, -3} 結果の配列には、追加された 1 つの余分な要素と共に正しいサブ配列要素が含まれます。条件が満たされないとき。

tldr:コードは出力サブ配列を次のように返します: {4 -1 -2 1 5 -3} 一方、正しい出力は {4, -1, -2, 1, 5} である必要があります

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int i, a[10], n, temp_sum=0, final_sum=0;
    vector<int> res;
    cin >> n;                               //getting array size input
    for(i=0; i<n; i++)
    {
        cin >> a[i];                        //getting array elements input
    }
    temp_sum=a[0];                          //initializing to first element
    final_sum=a[0];
    for(i=1; i<n; i++)
    {
        if(a[i]>temp_sum+a[i])       //if element is greater than sum so far
        {
            temp_sum = a[i];
            res.clear();
            res.push_back(a[i]);
        }
        else
        {
            temp_sum = a[i] + temp_sum;
            cout << temp_sum << " " << final_sum << " " << a[i] << "\n";
            res.push_back(a[i]);
        }
        if(temp_sum>final_sum)
        {
            final_sum = temp_sum;
        }
    }
    cout << final_sum << "\n";                  //displaying maximum sum
    for(i=0; i<res.size(); i++)                 //displaying result vector
    {
        cout << res[i] << " ";
    }
    return 0;
}
4

1 に答える 1

0

実行することに注意してください

res.push_back(a[i]);

if(temp_sum>final_sum)いずれにせよ、失敗した場合は res を更新しないでください

ちなみに、条件if(a[i]>temp_sum+a[i])は等しい temp_sum <0 （結果には影響しない）

于 2017-01-18T16:51:55.267 に答える