LeetCode 6

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/maximum-subarray
Il est possible de résoudre cet exercice en O(n).

Indice

Parcourir nums[i] en conservant deux variables : la somme maximum finissant en nums[i] et la somme maximum trouvée jusqu'à présent.

Voir algorithme de Kadane.

Solution

int maxSubArray(int* nums, int numsSize) {
    int maxi = nums[0], max_cur = nums[0];
    for(int i = 1; i < numsSize; i++) {
        // invariant : max_cur est la somme consécutive max qui se termine en i
        max_cur = max_cur + nums[i];
        if(max_cur < nums[i])
            max_cur = nums[i];
        if(max_cur > maxi)
            maxi = max_cur;
    }
    return maxi;
}