C++ Sliding Window Running Sum with explanation
Intuition\nTry dylan\'s index for each position with a one, calculate moves.\n\nAlways optimal to either\n1 - use all changes and pick closest for rest using op
# Intuition\nTry dylan\'s index for each position with a one, calculate moves.\n\nAlways optimal to either\n1 - use all changes and pick closest for rest using operation 2\n2 - if enough choices, only pick neighbors for operation 2 and use changes for getting rest of ones.\n\nThis is because change always requires 2 moves to gain 1 one (operation 1 + operation 2), which is only beat by having neighboring 1s.\n\nKeep track of a sliding window containing the closest k - 1 - maxChoices ones (k - 1 because starting at 1), keep a running sum of moves required to use operation 2 to get ones in the window.\n\nImplementation details is more complicated, but left and right are the parts of the window to the left and right of the current dylan index. Each index moved, the total move count changes by |left| - |right|.\n\n# Code\n```\nclass Solution {\npublic:\n    typedef long long ll;\n    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        ll minMoves = LLONG_MAX;\n        vector<int> arr;\n        for (int i = 0; i < nums.size(); ++i)\n            if (nums[i]) arr.push_back(i);\n        int n = arr.size();\n        if (n <= 1) return (k - (int)arr.size()) << 1;\n        --k; // account for starting at 1\n        \n        // account for adding neighbors and applying changes for all k\n        for (int i = 0; i < n; ++i) {\n            int nbs = (int)(i && arr[i-1] == arr[i]-1) + (int)(i != n-1 && arr[i+1] == arr[i]+1);\n            nbs = min(nbs, k);\n            int changes = max(k - nbs,0);\n            if (changes > maxChanges) continue;\n            minMoves = min(minMoves, (ll)(k << 1) - nbs);\n        }\n        cout << minMoves << endl;\n        \n        // need to track window size of k - maxChanges\n        deque<int> left;\n        deque<int> right;\n        int ws = k - maxChanges;\n        cout << "ws=" << ws << endl;\n        if (ws <= 0) return minMoves;\n        ll moves = maxChanges << 1;\n        int nextRight;\n        for (nextRight = 1; nextRight < n && right.size() < ws; ++nextRight) {\n            right.push_back(arr[nextRight] - arr[0]);\n            moves += arr[nextRight] - arr[0];\n        }\n        // cout << 0 << " " << moves << endl;\n        minMoves = min(minMoves, moves);\n        left.push_back(arr[0]);\n        \n        // pivots\n        for (int i = 1; i < n; ++i) {\n            int x = arr[i];\n            ll d = arr[i] - arr[i-1];\n            moves -= (ll)right.size() * d;\n            moves += (ll)left.size() * d;\n            right.pop_front();\n            while (nextRight < n && !left.empty() && ((x - left.front() >= arr[nextRight] - x) || right.empty())) {\n                moves -= x - left.front();\n                moves += arr[nextRight] - x;\n                right.push_back(arr[nextRight++]);\n                left.pop_front();\n            }\n            // cout << i << " " << moves << " " << left.size() << " " << right.size() << endl;\n            minMoves = min(minMoves, moves);\n            left.push_back(x);\n        }\n        return minMoves;\n    }\n};\n```
['Sliding Window', 'C++']