Algorithme de Kadane : sous-tableau maximum Leetcode

Intuition

Nous pouvons construire l'intuition sur la base de l'approche en deux points.

Approche

Nous allons commencer avec deux variables maxSum et maxTillNow.

• La première variable stocke la somme maximale que nous avons atteinte globalement dans le tableau.

• La deuxième variable stocke la valeur de la somme maximale atteinte jusqu'à l'index actuel. Étant donné que le tableau a une valeur négative, cette valeur fluctue, mais chaque fois que nous obtenons maxSum < maxTillMaintenant, nous mettons à jour le maxSum.

• Le dernier cas que nous devrons traiter sera celui où la somme maximale jusqu'à un indice atteint zéro, c'est-à-dire maxTillNow < 0, réinitialisez le maxTillNow = 0 à la fin de la boucle.

Complexité

• Complexité temporelle : O(N)

• Complexité spatiale : O(1)

Code

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 pour plus de solutions : Git
Profil Leetcode : Leetcode : devn007

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!