What is the minimal value for Ai?

0
Use DP ;)

"Let a commander and his subordinate have computers with numbers i and k respectively. According to the contract with the provider, the traffic between the computers i and k must be not less than Ai–Ak."
Can Ai-Ak<0 ?

You should consider both (Ai-Ak) and (Ak-Ai). Thus traffic >= max(Ai-Ak , Ak-Ai).

My AC solution assumes
Traffic = max(Ai-Ak, 0)