It is necessary to find a solution to this problem for O (n) or O (nlogn). The Kadana algorithm does not work, even if we look for the minimum modulo sum, divide and conquer, too. Below is the code I wrote.

private double Calculate(int left, int right, out int start, out int finish) { if (right == left) { start = left; finish = left; return arr[left]; } int s1 = left, f1 = right, s2, f2, s3, f3; int middle = (left + right) / 2; double leftmin = double.MaxValue; double rightmin = double.MaxValue; double temp = 0; for (int i = middle; i >= left; i--) { temp += arr[i]; if (Math.Abs(temp) < Math.Abs(leftmin)) { leftmin = temp; s1 = i; } } temp = 0; for (int i = middle + 1; i <= right; i++) { temp += arr[i]; if (Math.Abs(temp) < Math.Abs(rightmin)) { rightmin = temp; f1 = i; } } double leftans = Calculate(left, middle, out s2, out f2); double rightans = Calculate(middle + 1, right, out s3, out f3); double res = MinByAbs(MinByAbs(leftans, rightans), leftmin + rightmin); if (res == leftans) { start = s2; finish = f2; } else if (res == rightans) { start = s3; finish = f3; } else { start = s1; finish = f1; } return res; } private double MinByAbs(double a, double b) { if (Math.Abs(a) < Math.Abs(b)) return a; return b; }

arr is an array in class. For example, the code does not work if the array is {5, 6, -5, -6}

    1 answer 1

    We build a series of partial sums from the zero to the ith element — O (n).
    Our task is to find two identical sums (or as close as possible).
    We sort (with memorization of numbers in initial positions) - O (n log n).
    Now we pass through the sorted array, finding the minimum difference (or two identical elements) - O (n).

    Total - algorithm O (n log n) - same it seems suitable?

    A sketch on C ++ (C #, alas, I don’t know):

     vector<int> seq = { 5, 6, -5, -6, 2, 4 }; int main(int argc, const char * argv[]) { vector<pair<int,int>> sum(seq.size()); sum[0] = make_pair(seq[0],0); for(int i = 1; i < seq.size(); ++i) sum[i] = make_pair(sum[i-1].first+seq[i],i); sort(sum.begin(),sum.end()); int min = numeric_limits<int>::max(), idx = 0; // Тут приходится добавлять обработку нулевого индекса и нулевого значения... for(int i = 0; i < sum.size(); ++i) { int diff = abs(sum[i].first-((i == 0) ? 0 : sum[i-1].first)); if (diff < min) { min = diff; idx = i; } } cout << "min sum = " << min << " between [" << ((idx == 0) ? 0 : sum[idx-1].second+1) << "] and [" << sum[idx].second << "]\n"; }
    • And why - in the order of delirium? - Pavel Mayorov
    • Well, until I really checked the code ... :) - Harry