LeetCode 5

Deux exercices LeetCode pour ces vacances.

• Maximum Subarray : https://leetcode.com/problems/maximum-subarray. Il doit être résolu en complexité linéaire.
• Longest Palindromic Substring : https://leetcode.com/problems/longest-palindromic-substring.

Indice 1er exercice

Parcourir chaque indice du tableau en conservant la somme maximale se terminant à cet indice.

Indice 2ème exercice

Utiliser un algorithme par programmation dynamique en calculant b[i][j] qui vaut vrai si la sous-chaîne d'indice i à j est un palindrome.

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;
}

Solution

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* subword(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);
    bool** b = malloc(n*sizeof(bool*));
    for(int i = 0; i < n; i++) {
        b[i] = malloc(n*sizeof(bool));
        for(int j = 0; j < n; j++) {
            b[i][j] = true;
        }
    }

    int imax = 0, kmax = 0;
    for(int k = 1; k < n; k++)
        for(int i = 0; i < n - k; i++) {
            b[i][i + k] = s[i] == s[i + k] && b[i + 1][i + k - 1];
            if(b[i][i + k]) {
                kmax = k;
                imax = i;
            }
        }
    return subword(s, imax, imax + kmax);
}