Как мне запомнить это отношение повторения? - PullRequest
Новая
       100

Как мне запомнить это отношение повторения?

1 голос
/ 21 июня 2020

Я вычисляю Максимальная сумма подмассива с одним удалением на LeetCode:

Учитывая массив целых чисел, вернуть максимальную сумму для непустого подмассива (смежных элементов) с удалением не более одного элемента. Для ввода arr = [1,-2,0,3] вывод должен быть 4.

Я придумал рекурсивное решение, как показано ниже: 

class Solution {
public:
    int helper(vector<int>& n, vector<int>& cache, int startIndex) {
        if(startIndex>=n.size()) return INT_MIN;
        if(cache[startIndex]!=-1) return cache[startIndex];
        
        int allInclusiveSum=0, sumWithOneDel=0, lowestVal=INT_MAX, maxVal=INT_MIN;
        for(int i=startIndex; i<n.size(); i++) {
            allInclusiveSum+=n[i];
            maxVal=max(maxVal, allInclusiveSum);
            if(i!=startIndex) {
                lowestVal=min(lowestVal, n[i]);
                sumWithOneDel=allInclusiveSum-lowestVal;
                maxVal=max(maxVal, sumWithOneDel);
            }
        }
        
        maxVal=max(maxVal, helper(n, cache, startIndex+1));
        
        return cache[startIndex]=maxVal;
    }
    
    int maximumSum(vector<int>& arr) {
        int i=0, first=arr[0];
        for(i=1; i<arr.size(); i++)
            if(arr[i]!=first) break;
        if(i==arr.size()) return first;
        
        vector<int> cache(arr.size(), -1);
        return helper(arr, cache, 0);
    }
};

К сожалению, этот файл TLE. Поскольку я вызываю рекурсивно с помощью startIndex+1, я действительно не думаю, что сталкиваюсь с перекрывающимися подзадачами.

Есть ли способ запомнить свое решение? Если нет, то почему?

1 Ответ

0 голосов
/ 07 июля 2020

При программировании Dynami c мы просто определяем std::vector с N строками и двумя столбцами, затем пропускаем наш arr за один проход и используем std::max, чтобы найти max_sum: 

#include <vector>
#include <algorithm>


class Solution {
public:
    static inline int maximumSum(const std::vector<int> &arr) {
        int length = arr.size();
        std::vector<std::vector<int>> dynamic_sums(length, std::vector<int>(2, 0));
        dynamic_sums[0][0] = arr[0];
        int max_sum = arr[0];

        for (unsigned int row = 1; row < length; row++) {
            dynamic_sums[row][0] = std::max(arr[row], dynamic_sums[row - 1][0] + arr[row]);
            dynamic_sums[row][1] = std::max(arr[row], std::max(dynamic_sums[row - 1][1] + arr[row], dynamic_sums[row - 1][0]));
            max_sum = std::max(max_sum, std::max(dynamic_sums[row][0], dynamic_sums[row][1]));
        }

        return max_sum;
    }
};

Это аналогично O (N) времени и O (N) памяти.

Ссылки

...