<p>You have <code>n</code> super washing machines on a line. Initially, each washing machine has some dresses or is empty.</p>

<p>For each move, you could choose any <code>m</code> (<code>1 &lt;= m &lt;= n</code>) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.</p>

<p>Given an integer array <code>machines</code> representing the number of dresses in each washing machine from left to right on the line, return <em>the minimum number of moves to make all the washing machines have the same number of dresses</em>. If it is not possible to do it, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> machines = [1,0,5]
<strong>Output:</strong> 3
<strong>Explanation:</strong>
1st move:    1     0 &lt;-- 5    =&gt;    1     1     4
2nd move:    1 &lt;-- 1 &lt;-- 4    =&gt;    2     1     3
3rd move:    2     1 &lt;-- 3    =&gt;    2     2     2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> machines = [0,3,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong>
1st move:    0 &lt;-- 3     0    =&gt;    1     2     0
2nd move:    1     2 --&gt; 0    =&gt;    1     1     1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> machines = [0,2,0]
<strong>Output:</strong> -1
<strong>Explanation:</strong>
It&#39;s impossible to make all three washing machines have the same number of dresses.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == machines.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= machines[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:

    int max_sub(vector<int> &arr){
        int n = arr.size();
        vector<int> pref(n+1, 0);
        vector<int> suf(n+1, 0);
        int maxp=INT_MIN,maxs=INT_MIN,minp=INT_MAX,mins=INT_MAX;

        for(int i=0;i<n;i++){
            pref[i+1] = pref[i]+arr[i];
            if(abs(pref[i+1]) > maxp)maxp = abs(pref[i+1]);
        }
        for(int i=n-1;i>=0;i--){
            suf[i] = suf[i+1] + arr[i];
            if(abs(suf[i]) > maxs)maxs = abs(suf[i]);
        }
        cout << maxp << " " << maxs << endl;
        return(max(maxp,maxs));
    }

    int findMinMoves(vector<int>& mach) {
        int n = mach.size();
        if(n == 1)return(0);
        int sm = accumulate(mach.begin(), mach.end(), 0);
        if(sm%n != 0)return(-1);
        int target = sm/n;

        int ans = INT_MIN;
        vector<int> arr;
        bool isneg = mach[0] < target ? 1 : 0;
        int cur = abs(mach[0] - target);

        for(auto &t:mach){
            int c = t-target;
            if(c>=0)ans = max(ans,c);
            else ans = max(ans, (abs(c)+1)/2);
        }

        for(int i=1;i<n;i++){
            if(mach[i] < target && isneg){
                cur += target - mach[i];
                ans = max(ans, (cur+1)/2);
            }
            else if(mach[i] < target && !isneg){
                arr.push_back(cur);
                cur = target - mach[i];
                ans = max(ans, (cur+1)/2);
                isneg = 1;
            }
            else if(mach[i] >= target && !isneg){
                cur -= target - mach[i];
                ans = max(ans, (cur+1)/2);
            }
            else{
                arr.push_back(-cur);
                cur = mach[i] - target;
                ans = max(ans, (cur+1)/2);
                isneg = 0;
            }
        }
        if(isneg)arr.push_back(-cur);
        else arr.push_back(cur);

        return(max(ans, max_sub(arr)));
    }
};
16100