Блог пользователя subject17

Автор subject17, история, 2 года назад, По-английски

Hi, can anyone please help me with this problem: https://leetcode.com/problems/maximum-number-of-books-you-can-take/ I've come up with a working brute force approach (TLE): ```

// Time O(N^2)
long long maximumBooks(vector<int>& books) {
    long long res = 0;
    for (int i = 0; i < (int)books.size(); i++) {

        long long currentSum = 0;
        int lastVal = INT_MAX;

        for (int j = i; j >= 0; j--) {

            if (books[j] >= lastVal) {
                lastVal--;
                currentSum = (lastVal > 0) ? currentSum + lastVal : currentSum;
            }
            else {
                currentSum += books[j];
                lastVal = books[j];
            }

        }

        res = max(res, currentSum);
    }

    return res;
}

```

However, this problem can be solved in linear time according to this post: https://leetcode.com/problems/maximum-number-of-books-you-can-take/discuss/2508360/Java-O(n)-DP-%2B-Monotonic-Stack-oror-Beats-73-time-and-space-oror-Explanation-with-comments But I'm unable to understand how to calculate the summation as mentioned in the article Could someone please clarify/explain the linear time solution in plain English?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится