[Ежедневный алгоритм] Простой линейный DP и простое расширение | Месяц темы Python

Эта статья участвует в "Месяце тем Python", подробнее см.Ссылка на мероприятие

Описание темы

Это на LeetCodeМеч относится к предложению 42. Максимальная сумма последовательных подмассивов, трудность в томПростой.

Тег : "Линейное ДП"

Введите массив целых чисел, одно или несколько последовательных целых чисел в массиве образуют подмассив. Найдите максимальное значение суммы всех подмассивов.

Требуемая временная сложность $O(n)$ .

Пример 1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

намекать:

1 <= arr.length <= $10^5$
-100 <= arr[i] <= 100

динамическое программирование

Это простая линейная задача DP.

определение $f[i]$ рассматривать $nums[i]$ является максимальным значением подмассива в конце.

не теряя общий смысл $f[i]$ Как передать.

очевидно для $nums[i]$ С точки зрения подмассивов, оканчивающихся на него, возможны два случая:

$num[i]$ себя как независимый подмассив: $f[i] = nums[i]$ ;
$num[i]$ Он формирует подмассив с предыдущим значением.Поскольку это подмассив, его можно подключить только к $nums[i - 1]$ , Это: $f[i] = f[i - 1] + nums[i]$ .

наконец-то $f[i]$ Для двух вышеуказанных случаев возьмем $\max$ Просто:

f[i] = \max(nums[i], f[i - 1] + nums[i])

Java-код:

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0];
        int ans = f[0];
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(nums[i], f[i - 1] + nums[i]);
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

Код Python 3:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n
        ans = f[0] = nums[0]
        for i in range(1, n):
            f[i] = max(nums[i], f[i - 1] + nums[i])
            ans = max(ans, f[i])
        return ans

временная сложность: $O(n)$
Сложность пространства: $O(n)$

оптимизация пространства

Глядя на уравнение перехода состояния, мы находим, что $f[i]$ Явное значение зависит от $f[i - 1]$ .

Следовательно, мы можем использовать «конечные переменные» или «скользящие массивы», чтобы оптимизировать пространство для $O(1)$ .

Java-код:

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int max = nums[0], ans = max;
        for (int i = 1; i < n; i++) {
            max = Math.max(nums[i], max + nums[i]);
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[2];
        f[0] = nums[0];
        int ans = f[0];
        for (int i = 1; i < n; i++) {
            int a = i & 1, b = (i - 1) & 1;
            f[a] = Math.max(nums[i], f[b] + nums[i]);
            ans = Math.max(ans, f[a]);
        }
        return ans;
    }
}

Код Python 3:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = curMax = nums[0]
        for i in range(1, n):
            curMax = max(nums[i], curMax + nums[i])
            ans = max(ans, curMax)
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = nums[0]
        f = [ans, 0]
        for i in range(1, n):
            a, b = i & 1, (i - 1) & 1
            f[a] = max(nums[i], f[b] + nums[i])
            ans = max(ans, f[a])
        return ans

временная сложность: $O(n)$
Сложность пространства: $O(1)$

расширять

Интересное расширение состоит в том, чтодобавлениезаменитьумножение.

тема становится152. Максимальный подмассив продукта (умеренный).

Как мы должны это рассматривать?

Наивная идея, все еще учитывая определение $f[i]$ представлена $nums[i]$ это максимальное значение в конце, но есть ситуация, когда «отрицательное и отрицательное становятся положительными» для получения максимального значения, очевидно, недостаточно поддерживать максимальное значение префикса, мы можем ввести еще одно измерение $g[i]$ как минимум префикса.

Остальные разбор этого вопроса таким же образом.

Java-код:

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] g = new int[n + 1]; // 考虑前 i 个，结果最小值
        int[] f = new int[n + 1]; // 考虑前 i 个，结果最大值
        g[0] = 1;
        f[0] = 1;
        int ans = nums[0];
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            g[i] = Math.min(x, Math.min(g[i - 1] * x, f[i - 1] * x));
            f[i] = Math.max(x, Math.max(g[i - 1] * x, f[i - 1] * x));
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int min = 1, max = 1;
        int ans = nums[0];
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int nmin = Math.min(x, Math.min(min * x, max * x));
            int nmax = Math.max(x, Math.max(min * x, max * x));
            min = nmin;
            max = nmax;
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

Код Python 3:


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        g = [0] * (n + 1) # 考虑前 i 个，结果最小值
        f = [0] * (n + 1) # 考虑前 i 个，结果最大值
        g[0] = f[0] = 1
        ans = nums[0]
        for i in range(1, n + 1):
            x = nums[i - 1]
            g[i] = min(x, min(g[i-1] * x, f[i-1] * x))
            f[i] = max(x, max(g[i-1] * x, f[i-1] * x))
            ans = max(ans, max(f[i], g[i]))
        return ans

Наконец

Это первая статья из нашей серии «Пройдитесь по LeetCode».No.剑指 Offer 42Сериал стартует 01.01.2021.На момент старта на LeetCode 1916 вопросов, некоторые из которых заблокированы.Сначала закончим все вопросы без замков.

В этой серии статей, помимо объяснения идей решения проблем, будет дан максимально лаконичный код. Если речь идет об общих решениях, также будут предоставлены соответствующие шаблоны кода.

Чтобы облегчить студентам отладку и отправку кода на компьютере, я создал соответствующие склады:GitHub.com/sharing кислый….

В адресе склада вы можете увидеть ссылку на решение серии статей, соответствующий код серии статей, ссылку на исходный вопрос LeetCode и другие предпочтительные решения.