# Questions tagged [maximum-subarray]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
42 views

### Searching for the biggest area inside 2D matrix

so I've a algorytmical 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 ...
34 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 ...
93 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 ...
59 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 ...
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 \... 1answer 170 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) ... 2answers 980 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/... 0answers 266 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 ... 0answers 441 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) <... 1answer 310 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: ... 0answers 929 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 ... 1answer 374 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. ... 1answer 354 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 ... 2answers 152 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 =... 0answers 429 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 ... 1answer 19k 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 ... 0answers 157 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 ... 0answers 356 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 ...
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 ...