Rumah > Java > javaTutorial > Algoritma Kadane: Subarray Maksimum Leetcode

Algoritma Kadane: Subarray Maksimum Leetcode

DDD
Lepaskan: 2025-01-11 08:12:42
asal
815 orang telah melayarinya

Kadane

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;
    }
}
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan