Compute sum of longest positive subarray
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array that may contain positive and negative numbers, find the sum of the longest contiguous subarray consisting only of positive numbers. If multiple such subarrays share the maximum length, return the maximum sum among them. If the array contains no positive numbers, return 0. Explain the algorithm and its time and space complexity, and provide code in a language of your choice.
Quick Answer: Compute sum of longest positive subarray evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an integer array `nums` that may contain positive and negative numbers (and zeros), find the **sum of the longest contiguous subarray consisting only of positive numbers**.
Rules:
- A positive number is strictly greater than 0 (zero is NOT positive and breaks a run).
- If multiple positive subarrays share the maximum length, return the **maximum sum** among them.
- If the array contains no positive numbers, return `0`.
**Example 1**
```
Input: [1, 2, -1, 3, 4, 5, -2, 6]
Output: 12
```
The positive runs are [1,2] (len 2), [3,4,5] (len 3), and [6] (len 1). The longest is [3,4,5], so the answer is 3+4+5 = 12.
**Example 2 (tie on length)**
```
Input: [3, 4, -1, 10, 20]
Output: 30
```
Both [3,4] and [10,20] have length 2. Among the longest, the maximum sum is 10+20 = 30.
**Example 3 (no positives)**
```
Input: [-1, -2, -3]
Output: 0
```
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- A 'positive' number is strictly > 0; zero breaks a run.
- Return 0 when there are no positive numbers (including the empty array).
- On a length tie, return the maximum sum among the longest runs.
Examples
Input: [1, 2, -1, 3, 4, 5, -2, 6]
Expected Output: 12
Explanation: Positive runs: [1,2] (len 2), [3,4,5] (len 3), [6] (len 1). Longest is [3,4,5] -> 3+4+5 = 12.
Input: [-1, -2, -3]
Expected Output: 0
Explanation: No positive numbers, so the answer is 0.
Hints
- Scan left to right. Whenever you see a positive number, extend the current run (length += 1, sum += value); on any non-positive number, reset the current run to empty.
- Track the best answer as a (length, sum) pair. Update it when the current run is strictly longer, OR when it ties the best length but has a larger sum — that handles the tie-breaking rule.
- Initialize best length and best sum to 0 so that an array with no positives naturally returns 0 without a special case.