Problem
Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.
* The sub-arrays should not overlap.
eg- [2 -1 -2 1 -4 2 8] ans - (-1 -2 1 -4) (2 8), diff = 16
O(n) is required.
Solution
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
void FindMaxDiffSubArrays(int* arr, int len, int& maxStart, int& maxEnd, int& maxSum, int& minStart, int& minEnd, int& minSum)
{
minSum = arr[0];
maxSum = arr[0];
int currMinStart = 0;
int currMinEnd = 0;
int currMaxStart = 0;
int currMaxEnd = 0;
int currMinSum = 0;
int currMaxSum = 0;
for(int i = 0; i < len; ++i){
currMaxSum += arr[i];
if(maxSum < currMaxSum){
maxSum = currMaxSum;
}
else if (currMaxSum < 0){
currMaxSum = 0;
currMaxStart = i + 1;
}
if(currMaxSum == maxSum){
maxStart = currMaxStart;
maxEnd = i;
}
currMinSum += arr[i];
if(minSum > currMinSum){
minSum = currMinSum;
}
else if(currMinSum > 0){
currMinSum = 0;
currMinStart = i + 1;
}
if(currMinSum == minSum){
minStart = currMinStart;
minEnd = i;
}
}
}
void PrintArray(int* arr, int start, int end)
{
for(int i = start; i <= end; ++i){
cout << setw(5) << arr[i];
}
cout << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {-1, 2, -1, -2, 1, -4, 2, 8, -2, -1, 4, 7, 6, -2};
int maxStart, maxEnd, maxSum = 0, minStart, minEnd, minSum = 0;
for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i){
cout << setw(5) << arr[i];
}
cout << endl;
FindMaxDiffSubArrays(arr, sizeof(arr)/sizeof(arr[0]), maxStart, maxEnd, maxSum, minStart, minEnd, minSum);
cout << "The max sum of sub-array: " << maxSum << endl;
cout << "The sub-array " << endl;
PrintArray(arr, maxStart, maxEnd);
cout << "The min sum of sub-array: " << minSum << endl;
cout << "The min sum of sub-array " << endl;
PrintArray(arr, minStart, minEnd);
cout << endl;
int arr1[20];
for(int i = 10; i < 13; ++i){
cout << "The array is : " << endl;
for(int j = 0; j < i; j++){
arr1[j] = rand() % 20;
cout << setw(5) << arr1[j];
}
cout << endl;
FindMaxDiffSubArrays(arr1, i, maxStart, maxEnd, maxSum, minStart, minEnd, minSum);
cout << "The max sum of sub-array: " << maxSum << endl;
cout << "The sub-array " << endl;
PrintArray(arr1, maxStart, maxEnd);
cout << "The min sum of sub-array: " << minSum << endl;
cout << "The sub-array " << endl;
PrintArray(arr1, minStart, minEnd);
cout << endl;
}
return 0;
}
Output
-1 2 -1 -2 1 -4 2 8 -2 -1 4 7 6 -2
The max sum of sub-array: 24
The sub-array
2 8 -2 -1 4 7 6
The min sum of sub-array: -6
The min sum of sub-array
-1 -2 1 -4
The array is :
1 7 14 0 9 4 18 18 2 4
The max sum of sub-array: 77
The sub-array
1 7 14 0 9 4 18 18 2 4
The min sum of sub-array: 0
The sub-array
The array is :
5 5 1 7 1 11 15 2 7 16 11
The max sum of sub-array: 81
The sub-array
5 5 1 7 1 11 15 2 7 16 11
The min sum of sub-array: 1
The sub-array
1
The array is :
4 2 13 12 2 1 16 18 15 7 6 11
The max sum of sub-array: 107
The sub-array
4 2 13 12 2 1 16 18 15 7 6 11
The min sum of sub-array: 1
The sub-array
1
Press any key to continue . . .