Posted on by Kalkicode
Code Greedy

Longest subsequence having maximum sum

The Longest Subsequence with Maximum Sum problem involves finding a subsequence (not necessarily contiguous) from a given sequence of numbers such that the subsequence has the maximum possible sum. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Problem Statement and Example

Consider the sequence of numbers: [2, -4, 1, 3, -9, -5, -2, 0, 4]. The goal is to find a subsequence from this sequence that has the maximum sum. For this example, the subsequence [2, 1, 3, 0, 4] has the maximum sum of 10.

Idea to Solve the Problem

The problem can be solved by iterating through the given sequence of numbers while keeping track of the current sum and the maximum sum obtained so far. At each step, we decide whether to include the current element in the subsequence or not. If the current element increases the sum, we include it; otherwise, we reset the current sum to the current element. Additionally, we keep track of the starting and ending indices of the subsequence with the maximum sum.

Pseudocode

``````function longestMaxSeq(arr, n):
maxSum = arr[0]
currentSum = arr[0]
start = 0
end = 0
for i from 1 to n - 1:
if currentSum < 0:
currentSum = arr[i]
start = i
else:
currentSum += arr[i]
if currentSum > maxSum:
maxSum = currentSum
end = i
return start, end

# Main
arr = [2, -4, 1, 3, -9, -5, -2, 0, 4]
n = length(arr)
start, end = longestMaxSeq(arr, n)
print "Longest Sum Subsequence:", arr[start:end+1]``````

Algorithm Explanation

1. Initialize `maxSum`, `currentSum`, `start`, and `end` variables with the first element of the array.
2. Iterate through the array from the second element to the last.
3. If `currentSum` becomes negative, reset it to the current element and update the `start` index.
4. If `currentSum` is positive or zero, add the current element to it.
5. If `currentSum` becomes greater than `maxSum`, update `maxSum` and `end` index.
6. After iterating through the array, the subsequence with the maximum sum will be `arr[start:end+1]`.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the input array. This is because the algorithm iterates through the array once, performing constant-time operations at each step. The algorithm's efficiency lies in its ability to find the longest subsequence with the maximum sum in linear time.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post