11

たとえば、

{2,2,-1}, 
when k = 0, return -1.
when k = 3, return 3.

負の数と追加の変数 k があるため、これはさらに注意が必要です。k は任意の値、負の値にすることができます。仮定はしないでください。

この問題を解決するためにhttps://en.wikipedia.org/wiki/Maximum_subarray_problemとhttps://www.youtube.com/watch?v=yCQN096CwWMを参照できません。

どんな体でも私を助けることができますか？Java または JavaScript を使用することをお勧めします。

最大値 (変数 k なし) の古典的なアルゴリズム o(n) は次のとおりです。

public int maxSubArray(int[] nums) {

        int max = nums[0];
        int tsum = nums[0];
        for(int i=1;i<nums.length;i++){
            tsum = Math.max(tsum+nums[i],nums[i]);
            max = Math.max(max,tsum);
        }

        return max;
    }
4

6 に答える 6

0

これは、O(n²) で実行される単純なアルゴリズムです。

std::array<int, 3> input = {2, 2, -1};
int k = -1;
int sum = 0, largestSum = *std::min_element(input.begin(), input.end()) -1;
int i = 0, j = 0;
int start = 0, end = 0;

while (largestSum != k && i != input.size()) {
    sum += input[j];

    if (sum <= k && sum > largestSum) {
        largestSum = sum;
        start = i;
        end = j;
    }

    ++j;
    if (j == input.size()) {
        ++i;
        j = i;
        sum = 0;
    }
}

これは C++ ですが、Java や Javascript で書くのは難しくありません。基本的に、可能なすべての合計 ( がありますn*(n+1)/2) を試行し、k が見つかったら停止します。

largestSum十分に低い値に初期化する必要があります。入力の最小要素は k に等しい可能性があるため、1 を減算しました。
startとendは、最終的な部分配列の最初と最後のインデックスです。

もちろん、入力に制約があれば改善される可能性があります。

実際の例

于 2016-08-22T16:57:19.793 に答える