Questions tagged [maximum-subarray]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
19 views

Maximum Circular Subarray sum

This is a question from the book Algorithms by Jeff Erickson. Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a ...
4
votes
1answer
52 views

Find two contiguous subarrays with the greatest difference

Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn'...
1
vote
1answer
34 views

Maximum Subsequence Sum : Mark Weiss:

In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"? By ...
1
vote
1answer
56 views

Searching for the biggest area inside 2D matrix

I have an algorithmic problem where I need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions: Each pixel needs to be connected either diagonally or ...
1
vote
1answer
70 views

Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?

Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting ...
0
votes
0answers
115 views

How to find the length of maximum subarray sum in segment tree query?

Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
1
vote
1answer
276 views

Why finding the difference between the adjacent elements of the array to find the maximum difference?

I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum ...
4
votes
1answer
314 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
0
votes
1answer
214 views

Max subarray product

Is it possible to solve the max sub-array product problem using divide and conquer? Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) ...
1
vote
2answers
1k views

Understanding algorithm for maximum sum of non-consecutive elements

There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it: https://stackoverflow.com/questions/4487438/...
1
vote
0answers
331 views

Online algorithm to find shortest subarray containing all k-elements

We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each ...
1
vote
0answers
515 views

Algorithm to split an array into minimal number of subarrays where sum of their elements is less than or equal a given one

Title of the question pretty much summarises the question. Here is a concrete example of what I'm trying to achieve with no success. Let's say we have a sorted list (but sorted is not a requirement) <...
1
vote
1answer
369 views

Find maximum non contiguous subarray that respect a specific rule [closed]

Given these two arrays: [5, 3, 4, 1, 2] [1, 3, 2, 4, 5] Find the maximum subsequence in both arrays that the index of the elements are in a crescent order: ...
1
vote
0answers
1k views

Hint(s) please: Maximum Subarray O(n) solution CLRS Exercise 4.1-5

I've been stuck on this problem for some time, and I don't want to just look at an answer. I'd like a hint(s) so that I can get myself thinking in the right direction so that I might gain more insight ...
1
vote
1answer
404 views

Is the complement of a Max Prefix Sum a Min Suffix Sum?

Given an array A of n real numbers, are the maximum prefix sum and minimum suffix sum (and vice-versa) of A complements? I.e. ...
-1
votes
1answer
364 views

The longest subarray sum divisible by $5$ in $O(n)$ time

Given an array of non negative integers Find the longest continuous sub array which it's sum is divisible by 5. For example if the array is: [1,3,9,2,1,5,0,1] A continuous subarray which it's sum ...
0
votes
2answers
155 views

Sum of Maximum of continuous blocks of length k

Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k? Examples : A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10. A =...
2
votes
0answers
439 views

Maximal subarray problem with length constraint [duplicate]

I was recently faced with the following interview question: Given an array A, and an integer k, find a contiguous subarray with a maximal sum, with the added constraint this subarray has length ...
6
votes
1answer
24k views

What is a contiguous subarray?

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in ...
2
votes
0answers
159 views

Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a ...
5
votes
0answers
358 views

Subarray whose (sum × length) is maximum

Consider the following problem: Given an array of $n$ integer numbers (positive and negative), find a (contiguous) subarray for which the product $(\text{sum of the elements})\times(\text{length ...
7
votes
1answer
4k views

Maximum sub-matrix sum

Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array. The 1D version ...