Étant donné un tableau, trouvez la somme des plus grandes sous-séquences consécutives du tableau

La complexité temporelle est O(n)

Vous n'avez besoin de parcourir le tableau qu'une seule fois, mais vous devez comprendre en profondeur l'essentiel caractéristiques de ce tableau, c'est-à-dire la méthode de programmation dynamique.

Définissez d’abord deux variables, thisSum et maxSum. Parmi eux, thisSum représente la somme des éléments atteignant la position actuelle ; maxSum représente la somme maximale des sous-séquences consécutives atteignant la position actuelle.

Remarque : si thisSum est négatif, définissez-le directement sur 0 ; si thisSum est supérieur à maxSum, définissez maxSum sur la valeur de thisSum.

public static int maxSubArray(int[] nums)
    {
        int length = nums.length;
        if(length <= 0)
            return 0;
        int CurSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < length; i++)
        {
            if(CurSum <= 0)     //当当前的和小于等于0，那么就给其置为当前元素的值
                CurSum = nums[i];
            else
                CurSum += nums[i];
            if(CurSum > max)
                max = CurSum;
        }
        return max;
    }

Tutoriel recommandé : Tutoriel PHP

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!