# Questions tagged [maximum-subarray]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
28 views

### Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this: ...
139 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: ...
69 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 ...
70 views

231 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) ...
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/...
358 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 ...
550 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) <...
400 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: ...
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 ...
429 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. ...
370 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 ...
157 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 =...
465 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 ...
26k 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 ...