Algoritma Kadane: Subarray Maksimum Leetcode

Intuisi

Kita boleh membina gerak hati berdasarkan pendekatan dua mata.

Pendekatan

Kami akan bermula dengan dua pembolehubah maxSum dan maxTillNow.

• Pembolehubah pertama menyimpan jumlah maksimum yang telah kita capai secara keseluruhan dalam tatasusunan.

• Pembolehubah kedua menyimpan nilai jumlah maksimum yang dicapai sehingga indeks semasa. Memandangkan tatasusunan mempunyai nilai negatif, nilai ini akan turun naik, tetapi apabila kita mendapat maxSum < maxTillNow, kami mengemas kini maxSum.

• Kes terakhir yang perlu kami tangani ialah jika jumlah maksimum sehingga mana-mana indeks mencapai sifar, iaitu, maxTillNow < 0, tetapkan semula maxTillNow = 0 pada penghujung gelung.

Kerumitan

• Kerumitan masa: O(N)

• Kerumitan ruang: O(1)

Kod

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}

Repo GitHub untuk lebih banyak penyelesaian: Git
Profil Leetcode: Leetcode: devn007

Atas ialah kandungan terperinci Algoritma Kadane: Subarray Maksimum Leetcode. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!