各区画の生産力を計算し、その最大値と最小値の差を求めればよいです。 制約より、\(M\) 個の区画は畑 \(1\) から畑 \(N\) までを重複なく過不足なく分割します。そのため、区画の長さの合計は \(N\) です。

よって、各区画について愚直にその生産力を計算しても全体で時間計算量 \(\mathrm{O}(N)\) しかかかりません。

よって、全体で\(\mathrm{O}(N+M)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& e : a) cin >> e;
    long long ma = 0, mi = 1e18;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        l--;
        long long sum = 0;
        for (int i = l; i < r; ++i) sum += a[i];
        ma = max(ma, sum);
        mi = min(mi, sum);
    }
    cout << ma - mi << endl;
}