I have a question that I can't understand.

Solution said we should iterate x which is the number of subarrays with maximum sums that we will use. But what will we do if we have two subarrays with equal sums?

for example

4 3
-11 16 -11 -1

We will choose 16 for sure. Then we have two options. One is -11 16 and 16 -11 -1, the other is 16 -11 and -11 16 -11 -1. The first one has a better answer.

izban proved that if some pair of subsegments have same sum, it doesn't matter when we choose first $$$k - n$$$ subarrays. But his proof is not correct when we choose $$$> k - n$$$ subarrays.

The statement shows "not available on English language" and the tutorial shows "Unable to parse markup [type=CF_TEX]". What happened?

Many participants use std::map in their codes.

If the type of the key is int, it will be hacked by this:

2
2 1 2
10 0 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 589934621

Because (int) 4294967296LL == 0

One day when I had my math class,I came up with an idea.But I found that I can't solve it.

After class I asked many people but they did't solve it too.

Here's the problem:

You are given a undirected weighted graph with n nodes and m edges.

You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.

A simple path means that you can't pass through one edge twice or more.

(I don't know how large n,m can be)

Update:Thanks to TimonKnigge,we can solve it in $$$O(m^2 \times n^3)$$$