StriverのSDEシート・ジャーニー

8065 ワード
computerscience programming beginners java テキストリンク
ハイ👋DEVS
前のポストでは、我々は解決して、問題を理解しました、そして、このポストでは、我々は次の1つのKadaneのアルゴリズムに取り組みます.

菅四貫種のアルゴリズム
この問題で、私たちは整数配列numsを与えました.そして、隣接しているサブアレイ(少なくとも1つの数を含む)を見つけます.

Example 1:


入力: nums =[ - 2 , 1 , - 3 , 4 , - 1 , 2 , 1 , - 5 , 4 ]
生産:6説明:［4,−1,2,1］は合計＝6となる.

Example 2:


入力: nums = [ 1 ]
生産:1
解決策
この問題をKadaneのアルゴリズムを使って簡単に解くことができます.
ステップでKadaneのアルゴリズムのステップを議論しましょう.
Step 1は3つのINT変数sum = 0、max = nums[0]、arrSize = nums.lengthを初期化します.
Step 2はi = 0からarrSizeまでのループを実行します.

1. sum = sum + nums[i].
2. if sum > max then max = sum.
3. if sum < 0 then sum = 0.


ステップ3リターンmaxステップ4エンドsum = 0ならばなぜsum < 0を再初期化するか?
負の合計は、最大合計に貢献することはありませんので、値を0に再初期化し、次の要素
Javaでこのアルゴリズムをコーディングする前に、このAlgoのより良い理解のためにこのイメージを見てください.

Java


class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;

        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];

            if(sum > max){
                max = sum;
            }

            if(sum < 0) {
                sum =0
            }
        }

        return max;

}
}
でもどうやって?私たちは知っている.
マックスサブアレイの長さ
  • MAXサブアレイ
    • のスタート＆エンドインデックス
    マックスサブアレイの
  • 要素
    したがって、これらのために、我々は2つのより多くのINT変数firstIndexとlastIndexを作成することができます.

    step-2 run a loop from i = 0 to arrSize.

    1. sum = sum + nums[i].
    2. if sum > max then max = sum,lastIndex = i.
    3. if sum < 0 then sum = 0, firstIndex = i+1.

    firstIndexとlastIndex変数を使用することで、我々は、次の質問に答えることができます.
  • サブアレイの長さ.subArrSize = lastIndex - firstIndex
  • サブアレイの開始と終了インデックス.firstIndexとlastIndex変数
    • を使用することによって
    マックスサブアレイの
  • 要素.firstIndexからlastIndexまで、我々は要素
    • を見つけることができます

    Java


    class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;
        int firstIndex = 0,lastIndex = 0;

        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];

            if(sum > max){
                max = sum;
                lastIndex = i;
            }
            if(sum < 0) {
                sum =0;
                firstIndex = i + 1;
            }
        }

        return max;

}
}

    Time Complexity⏱️


    forループを0からarrsizeに実行します.
    したがって、O ( arrsize )は時間の複雑さです.

    Space Complexity⛰️


    algoは余分なスペースを使用していません.
    この記事が好きならコメント欄で教えてください.
    あなたがポストで何か間違っているとわかるならば、plzは私を正します.
    私の記事を読んでくれてありがとう.
    • [Effective C++] Ch1. C++であれば、C++の方法に従います.
    ジャンプ2 Python 5強-Pythonの翼を差し込む