River Current

Problem Statement

River Current A river is divided into N consecutive sections, numbered 0 through N-1 . Section i carries a current C[i] : C[i] > 0 — the current flows to the right , with strength C[i] . C[i] < 0 — the current flows to the left , with strength |C[i]| . C[i] = 0 — the section is stagnant . Every stagnant section is pulled by the two nearest sections that actually carry a current: the nearest non-zero section somewhere to its left, and the nearest non-zero section somewhere to its right. A run of several adjacent zeros is therefore influenced by the same pair of non-zero currents — the ones just outside the run — no matter how long the run is. For a stagnant section with left influence a and right influence b , the net current is decided by strength alone , never by distance: If only one of the two influences exists (the run touches an end of the river), that influence is used. If neither exists (the whole river is stagnant), the section stays 0 . If |a| > |b| , the result is a