To find the minimum positive contiguous subsequence in an array in O(n) time, we can leverage a variant of Kadane's algorithm, which is typically used to find the maximum sum subarray. We focus on identifying the smallest positive sum subarray instead. This solution requires careful tracking of sums to isolate the smallest positive segment efficiently.

Algorithm Overview

1. Initialization:
   • Start with an accumulator to keep track of the current subarray sum.
   • Use a variable to store the minimum positive sum found so far.
   • A flag is set to check whether any positive sum has been encountered.
2. Iterate through each element:
   • Add current element to the current sum.
   • Check if the current sum is positive and smaller than the current minimum positive sum, update the minimum positive sum.
   • If the current sum becomes non-positive, reset it to zero since we are looking for positive sums.
   • This approach will ensure that you traverse each element once, giving you an O(n) complexity.
3. Edge Cases:
   • If no positive sum is found throughout the array, it's essential to handle this scenario separately by checking the flag.

Step-by-Step Example

Let's consider an example to demonstrate the approach:

Example Array:

$$3, -1, 4, -2, 5, -9, 3$$

1. Initialization:
   • current_sum = 0
   • min_positive_sum = +\infty
   • positive_found = False
2. Iterate through each element:
   • Element: 3
     current_sum = 3
     min_positive_sum = 3
     positive_found = True
   • Element: -1
     current_sum = 2
     min_positive_sum = 2
   • Element: 4
     current_sum = 6
     • No update, as 6 is not less than 2.
   • Element: -2
     current_sum = 4
     • No update, as 4 is not less than 2.
   • Element: 5
     current_sum = 9
     • No update as 9 is not less than 2.
   • Element: -9
     current_sum = 0
     • Reset since the sum has become non-positive.
   • Element: 3
     current_sum = 3
     • No update as 3 is not less than 2 (but at this position, the current sum restarts).
3. Final Result:
   • Minimum positive contiguous subsequence sum is 2, which is the subsequence $$3, -1$$.

Pseudocode