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].

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.