Questions tagged [maximum-subarray]
The maximum-subarray tag has no summary.
37 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
0
answers
39
views
Find all non-extendable ranges in an array of real values with a non-positive sum
I have a long array of size $n>10^6,ドル call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions
$\sum_{i=a}^{b-1}X[i] \leq 0,ドル
$b-a \geq K,ドル
$\sum_{i=a-1}^{b-1} X[i]...
1
vote
1
answer
575
views
Find the smallest subarray with sum larger than a threshold
Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T,ドル find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
0
votes
1
answer
417
views
Find and keep minimum and maximum values in circular buffer structure
The circular buffer is filled with data one value at a time. The buffer size is N elements (let's take 3 as an example). Is there an algorithm that allows you to always know what is the minimum and ...
1
vote
1
answer
109
views
maximum span between two numbers
We have an array of n measurements: (m_0, m_1, ..., m_n-1). The measurements are voltages, but that's not important, so let's ...
1
vote
1
answer
1k
views
Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
1
vote
1
answer
359
views
Single machine scheduling with profit and deadline constraints
The problem is described as such:
Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’.
So for some $i \in \{1,\ldots , n\},ドル $J_i=\{t_i,p_i\}$ where $t_i$ is the ...
0
votes
1
answer
101
views
Maximal Profit of 'legal' cutting of a board
I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill.
Given a board of length $n,ドル and an increasing ...
1
vote
1
answer
221
views
How can I convert the pseudo-code that solves maximum subarray problem to Python code?
I'm reading Algorithm Design and Application, by Michael T. Goodrich and Robert Tamassia, and sometimes the pseudo-code in this book doesn't make sense at all.
At chapter one they show us 3 solutions ...
0
votes
2
answers
5k
views
Maximum subarray sum of given length range
Can anyone please help me solve this better than $O(|a-b| \cdot n)$?
Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
0
votes
3
answers
302
views
How do i delete one single unequal element from an array of equal elements without using hashing?
The rules of the question state that:
Only one element is different.
Rest are all same.
Array A size is 8.
I need to find the different element and remove it (Hashing cannot be used).
I have not ...
1
vote
1
answer
482
views
Finding a maximum subarray in worst-case linear time
Here's a problem of CLRS:
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, ...
0
votes
0
answers
84
views
Time complexity about Maximum subarray
I recently came across a function called the strawman algorithm which the pseudo code looks like this:
...
2
votes
2
answers
2k
views
Find the length of the longest subarray having sum greater than k
I tried to solve this problem but could not do it better than $O(n^2)$.
My Algorithm:
...
2
votes
2
answers
1k
views
What is exactly an empty Sub-array
I read the question in Exercise 4.1-4 in Introduction To Algorithms:
Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the ...
2
votes
1
answer
137
views
Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem
I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:
We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $...