918. Maximum Sum Circular Subarray

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium

LeetCode Static

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]

Output: 3

C# решение

сопоставлено/оригинал

public class Solution {
    public int MaxSubarraySumCircular(int[] nums) {
        int Kadane(int[] arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.Length; i++) {
                currentSum = Math.Max(arr[i], currentSum + arr[i]);
                maxSum = Math.Max(maxSum, currentSum);
            }
            return maxSum;
        }
        int maxKadane = Kadane(nums);
        int totalSum = nums.Sum();
        int minKadane = Kadane(nums.Select(num => -num).ToArray());
        return Math.Max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxSubarraySumCircular(vector<int>& nums) {
        int Kadane(vector<int>& arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.size(); i++) {
                currentSum = max(arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        }
        int maxKadane = Kadane(nums);
        int totalSum = nums.Sum();
        int minKadane = Kadane(nums.Select(num => -num).ToArray());
        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int kadane(int[] arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.length; i++) {
                currentSum = Math.max(arr[i], currentSum + arr[i]);
                maxSum = Math.max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        int minKadane = kadane(Arrays.stream(nums).map(num -> -num).toArray());

        return Math.max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
}

JavaScript решение

сопоставлено/оригинал

var maxSubarraySumCircular = function(nums) {
    const kadane = (arr) => {
        let currentSum = arr[0], maxSum = arr[0];
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    };

    const maxKadane = kadane(nums);
    const totalSum = nums.reduce((a, b) => a + b, 0);
    const minKadane = kadane(nums.map(num => -num));

    return Math.max(maxKadane, totalSum + minKadane === 0 ? maxKadane : totalSum + minKadane);
};

Python решение

сопоставлено/оригинал

def maxSubarraySumCircular(nums):
    def kadane(arr):
        current_sum = max_sum = arr[0]
        for num in arr[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum

    max_kadane = kadane(nums)
    total_sum = sum(nums)
    min_kadane = kadane([-num for num in nums])

    return max(max_kadane, total_sum + min_kadane if total_sum + min_kadane != 0 else max_kadane)

Algorithm

Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.