Tap here to switch tabs
Problem
Submissions

Problem: Maximum Coin Collection

Maximum Coin Collection gives two lane arrays with coin values that may be negative. Find the most coins in a contiguous trip starting in lane1, with at most one switch into lane2 and one back.

Statement

You are given two integer arrays lane1 and lane2 of equal length, representing the number of coins available at each mile along a two lane freeway.

Mario drives along a contiguous stretch of the freeway covering at least 11 mile. He travels according to the following rules:

  • He starts driving in lane1.

  • He may switch to lane2 at most once.

  • After driving in lane2, he may switch back to lane1 at most once.

  • He cannot switch back to lane2 again.

In other words, his journey consists of up to three consecutive segments: an initial segment in lane1, a middle segment in lane2, and a final segment in lane1. Any of these segments may be empty, but the total distance driven across all chosen segments must be at least 11 mile.

Return the maximum total number of coins Mario can collect.

Constraints:

  • 1≤1 \leq lane1.length == lane2.length ≤105\leq 10^5

  • −109≤-10^9 \leq lane1[i], lane2[i] ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Coin Collection

Maximum Coin Collection gives two lane arrays with coin values that may be negative. Find the most coins in a contiguous trip starting in lane1, with at most one switch into lane2 and one back.

Statement

You are given two integer arrays lane1 and lane2 of equal length, representing the number of coins available at each mile along a two lane freeway.

Mario drives along a contiguous stretch of the freeway covering at least 11 mile. He travels according to the following rules:

  • He starts driving in lane1.

  • He may switch to lane2 at most once.

  • After driving in lane2, he may switch back to lane1 at most once.

  • He cannot switch back to lane2 again.

In other words, his journey consists of up to three consecutive segments: an initial segment in lane1, a middle segment in lane2, and a final segment in lane1. Any of these segments may be empty, but the total distance driven across all chosen segments must be at least 11 mile.

Return the maximum total number of coins Mario can collect.

Constraints:

  • 1≤1 \leq lane1.length == lane2.length ≤105\leq 10^5

  • −109≤-10^9 \leq lane1[i], lane2[i] ≤109\leq 10^9