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
- Initialize
maxSum
,currentSum
,start
, andend
variables with the first element of the array. - Iterate through the array from the second element to the last.
- If
currentSum
becomes negative, reset it to the current element and update thestart
index. - If
currentSum
is positive or zero, add the current element to it. - If
currentSum
becomes greater thanmaxSum
, updatemaxSum
andend
index. - After iterating through the array, the subsequence with the maximum sum will be
arr[start:end+1]
.
Code Solution
-
1) Longest subsequence with maximum sum in java
2) Longest subsequence with maximum sum in c++
3) Longest subsequence with maximum sum in c
4) Longest subsequence with maximum sum in c#
5) Longest subsequence with maximum sum in php
6) Longest subsequence with maximum sum in python
7) Longest subsequence with maximum sum in ruby
8) Longest subsequence with maximum sum in scala
9) Longest subsequence with maximum sum in swift
10) Longest subsequence with maximum sum in kotlin
11) Longest subsequence with maximum sum in node js
12) Longest subsequence with maximum sum in golang
13) Longest subsequence with maximum sum in vb.net
14) Longest subsequence with maximum sum in typescript
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.
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.
New Comment