DoubleHelix SPOJ

Problem Statement

Two DNA sequences are given as two arrays of integers. The sequences intersect at certain points (where they have the same value). You can switch from one sequence to another only at intersection points.

Find the maximum possible sum when traversing from the start to the end, switching optimally between sequences.

Constraints:

• 1 ≤ n, m ≤ 10^5
• Both arrays are sorted in ascending order
• Values are positive integers

Example:

• Input:
  • seq1 = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62]
  • seq2 = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100]
• Output: 450
• Explanation: Intersection points are 7, 25, 55, 57. Optimal path switches at these points to maximize sum.

Example 2:

• Input:
  • seq1 = [1, 2, 3]
  • seq2 = [2, 3, 4]
• Output: 10
• Explanation: Path: 1 → 2 → switch → 3 → 4 = 10 (or stay on seq1: 1+2+3=6, stay on seq2: 2+3+4=9)

Approach 1: Brute Force (Find All Paths)

Intuition

Find all intersection points, then try all possible combinations of switches to find the maximum sum.

Algorithm

1. Find all intersection points using nested loops
2. Try all 2^k combinations (switch or not at each intersection)
3. Calculate sum for each path and track maximum

public class Solution {
    public long maxSumBrute(int[] seq1, int[] seq2) {
        // Similar implementation
        return 0; // Placeholder
    }
}

Complexity Analysis

• Time Complexity: O(n × m) for finding intersections + O(2^k) for paths
• Space Complexity: O(n + m) for storing sequences

Approach 2: Two Pointers with Segment Sums (Optimal)

Intuition

Use two pointers to traverse both sequences simultaneously. Between any two consecutive intersection points, we have two path options - calculate both and take the maximum.

Key Observations:

1. Both sequences are sorted
2. At each intersection, we can choose either path
3. Between intersections, we must stay on one sequence
4. Greedy choice: at each intersection, take the path with higher segment sum

Algorithm

1. Use two pointers i, j starting at 0
2. Move the pointer with smaller value, accumulating sums
3. When values are equal (intersection), add max of both segment sums
4. Continue until both sequences are exhausted

public class DoubleHelix {
    public long maxSum(int[] seq1, int[] seq2) {
        int n = seq1.length, m = seq2.length;
        int i = 0, j = 0;
        
        long sum1 = 0, sum2 = 0;
        long result = 0;
        
        while (i < n && j < m) {
            if (seq1[i] < seq2[j]) {
                sum1 += seq1[i];
                i++;
            } else if (seq1[i] > seq2[j]) {
                sum2 += seq2[j];
                j++;
            } else {
                // Intersection point
                sum1 += seq1[i];
                sum2 += seq2[j];
                
                result += Math.max(sum1, sum2);
                
                sum1 = 0;
                sum2 = 0;
                
                i++;
                j++;
            }
        }
        
        while (i < n) {
            sum1 += seq1[i];
            i++;
        }
        
        while (j < m) {
            sum2 += seq2[j];
            j++;
        }
        
        result += Math.max(sum1, sum2);
        
        return result;
    }
    
    public static void main(String[] args) {
        DoubleHelix dh = new DoubleHelix();
        int[] seq1 = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62};
        int[] seq2 = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100};
        System.out.println(dh.maxSum(seq1, seq2));  // Output: 450
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n + m) - Single pass through both arrays
• Space Complexity: O(1) - Only using variables

SPOJ Solution Template

Visualization

Key Takeaways

1. Two Pointers on Sorted Arrays: Classic technique for merging/comparing sorted arrays
2. Greedy at Intersections: Always take the path with higher segment sum
3. Segment Sums: Track cumulative sums between intersection points
4. Include Intersection: Add intersection value to both segment sums before comparing
5. Handle Remainders: After loop, process remaining elements in both arrays
6. Single Pass: O(n + m) is optimal for this problem
7. DNA Analogy: Think of it as choosing the best "strand" to follow