If there are \$n\$ stations then your approach takes \$O(n^2)\$ time. I can't see a \$O(n)\$ time algorithm, but there is a simple \$O(n \log n)\$ time one:

Define \$S(i) = p_1 + p_2 + ... + p_i\$. Then you're trying to find \$s\$ and \$e\$ to minimise \$|S(e) - S(s)|\$. If you sort the values of \$S(i)\$ in \$O(n \log n)\$ time, the minimum difference will be between two consecutive values, so you can do a linear scan to find it.

If there are \$n\$ stations then your approach takes \$O(n^2)\$ time. I can't see a \$O(n)\$ time algorithm, but there is a simple \$O(n \log n)\$ time one:

Define \$S(i) = p_1 + p_2 + \ldots + p_i\$. Then you're trying to find \$s\$ and \$e\$ to minimise \$|S(e) - S(s)|\$. If you sort the values of \$S(i)\$ in \$O(n \log n)\$ time, the minimum difference will be between two consecutive values, so you can do a linear scan to find it.

If there are n stations then your approach takes O(n^2) time. I can't see a O(n) time algorithm, but there is a simple O(n lg n) time one:

Define S(i) = p1 + p2 + ... + pi. Then you're trying to find s and e to minimise |S(e) - S(s)|. If you sort the values of S(i) in O(n lg n) time, the minimum difference will be between two consecutive values, so you can do a linear scan to find it.

If there are \$n\$ stations then your approach takes \$O(n^2)\$ time. I can't see a \$O(n)\$ time algorithm, but there is a simple \$O(n \log n)\$ time one:

Define \$S(i) = p_1 + p_2 + ... + p_i\$. Then you're trying to find \$s\$ and \$e\$ to minimise \$|S(e) - S(s)|\$. If you sort the values of \$S(i)\$ in \$O(n \log n)\$ time, the minimum difference will be between two consecutive values, so you can do a linear scan to find it.