FAKU
Reputation: 1
Given a sequence, for each k, find a set of k disjoint continuous subsequences that the total sum of all elements in the set is maximized
Given a integer sequence of length n, for each k, how to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. Is there a linear algorithm ?
We got a algorithm of O (n log n), and we can solve the problem for a certain k in O (n) (Found here). But we're not sure if this problem can be solved in O (n).
Upvotes: -5
Views: 45
Answers (0)
Related Questions
- Challenge: How to store a large number of sets to quickly calculate the sum of the values taken by the elements in each set?
- Cut a sequence of length N into subsequences such that the sum of each subarray is less than M and the cut minimizes the sum of max of each part
- Given an input array find all subarrays with given sum K
- Number of all increasing subsequences in given sequence?
- Optimize: Divide an array into continuous subsequences of length no greater than k such that sum of maximum value of each subsequence is minimum
- Subset Sum algorithm
- Given a positive integer array, find starting indexes of contiguous subsequences of length L that their sum equals to S
- Given a sequence of n positive integers, find a subsequence of length k such that the sum over the absolute values of the differences is maximal
- Maximum total sum of non-overlapping intervals with total weight W
- Find contiguous subsequences such that cube of the sum of numbers is at most y