All Questions
Tagged with sub-array dynamic-programming
17 questions
1
vote
5
answers
4k
views
Finding the subarray with the Maximum sum in the given ArrayList
The problem description:
Given an ArrayList of Integers. Find a subarray with the maximum sum of any potential subarray within the ArrayList.
A subarray a is a combination of consecutive numbers.
The ...
- 77
1
vote
2
answers
2k
views
Maximum difference of sum of odd and even index elements of a subarray
Given an array of N integers (can be positive/negative), calculate the maximum difference of the sum of odd and even indexed elements of any subarray, assuming the array follows 0 based indexing.
For ...
2
votes
2
answers
2k
views
How to find all contiguous sub array combinations of an array and print it
I need to write a program to print all sub arrays of an array in a particular format.
Example-
I/o:
n = 3
A = (1,2,3) where n is the size of the array and A is the array itself.
O/p:
(1),(2),(3)
(1),...
- 35
4
votes
2
answers
3k
views
How can I divide an array into K sub-arrays such that the sum of the number of duplicate elements in all the sub-array is minimum?
As an example, let the array be A={1,1,2,1,2} and K=3. A can be divided into {1}, {1,2} and {1,2}. So, number of duplicate elements in those sub-arrays is 0, 0 and 0. So, the sum of them is 0.
0
votes
1
answer
342
views
Find maximum product subarray
We need to Find the contiguous subarray within an array (containing at least one number) which has the largest product and return an integer corresponding to the maximum product possible.
I found this ...
- 183
0
votes
1
answer
119
views
Count of sub-arrays with a given sum such that the indices are in ascending order
Given an array, count the number of sub-arrays with a given sum such that the indices are in ascending order (They do not need to be continuous, but the indices of the elements of the array should be ...
0
votes
1
answer
1k
views
Finding the Number of Quadruples
In this problem you are given a sequence of N positive integers S[1],S[2],…,S[N]. In addition you are given an integer T, and your aim is to find the number of quadruples (i,j,k,l), such that 1 <= ...
- 117
0
votes
1
answer
20
views
Getting timeout error for min_sub_array_sum?
I am getting this kind of weird error, I wrote a function to find the minimum sub array sum. But this doesn't work when the values of array start from 1 to size for value 1 2 3 4. I get timeout, but ...
2
votes
1
answer
2k
views
Count Number of distinct subarrays
I recently came across this question in one of the coding interviews. The question is as follows:
Given an array A[] of n numbers and a number k, count the total number of distinct subarrays such ...
- 4,225
3
votes
1
answer
176
views
Making Maximum Length Ascending Sub array from an array with only 3 valid moves
I need to solve this problem with DP and here is the problem:
we have an array and we want to make a ascending sub array with maximum size with 2 conditions:
We can just traverse the array one time ...
5
votes
5
answers
7k
views
Maximum sum of contiguous sub-sequence with length at most k
I am trying to modify the Kadane Algorithm in order to solve a more specific problem.
def max_Sum(arr, length, k):
if length < k:
print('length of array should be greater than k')
res = 0
...
- 187
1
vote
1
answer
564
views
Traversing all the subarrays of a 2-D array
I have a 2-D array given of size P*Q and I have to answer K questions based on the array. The 2-D array given consists of numbers 0 and 1. For each question, we have to count the maximum size of any ...
- 59
-1
votes
1
answer
544
views
How to find the longest contiuous subarray whose XOR is 0
For example, given {1,1,2,2}:
the XOR of these subarrays are all 0: {1,1} , {2,2} , {1,1,2,2}.
The length of the longest is 4.
Find the length of the longest subarray and return the beginning and ...
- 19
0
votes
1
answer
699
views
Find maximum sum contiguous subarray such that the length of the subarray is less than equal to k?
If more than two subarrays exist we need to return the subarray that has lesser length.
We are only concerned with length of the subarray and its sum.
I know this can be solved in O(n^2) using ...
- 893
1
vote
0
answers
179
views
What is the approach to solve spoj KPMATRIX?
The problem link is here. The problem is basically to count all such sub matrices of a given matrix of size N by M, whose sum of elements is between A and B inclusive. N,M<=250. 10^-9<=A<=B&...
- 524