Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [maximum-subarray]

The tag has no usage guidance.

0
votes
0answers
50 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
22 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
120 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
112 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) ...
0
votes
2answers
691 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
200 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
333 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
242 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
797 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
342 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
340 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
148 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
422 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 ...
5
votes
1answer
15k 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
152 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
351 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 ...
6
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 ...