sameep
BAN USERhere's a O(n) solution:
// {1, 2, -5, 10, 0, - 15, -1, 3, -4}
// maximize 10 - (-17)) = 27
// let's consider a pointer that moves through the set which breaks set into two
// regions - left and right which are subsets
// for each of these subsets we want to consider max and min values
// and then use the ones that give best possible diff
// following structure keeps track of max and min for a given subset
struct elem {
int maxsum;
int minsum;
int min;
int max;
elem() : maxsum(0), minsum(0), min(0), max(0) {}
elem& operator = (int a) { maxsum = a; minsum = a; min = a; max = a; return *this; }
elem& operator + (int a) { maxsum+=a; if (maxsum < 0) maxsum = 0; if (maxsum > max) max = maxsum;
minsum+=a; if (minsum > 0) minsum = 0; if(minsum < min) min = minsum; return *this; }
};
int maxdiffinsubsets(int A[], int size)
{
elem *DA1 = new elem [size - 1];
elem* DA2 = new elem [size - 1];
int i;
int bestdiff = 0;
// create a dynamic array that stores min and max of all possible subsets
DA1[0] = A[0];
for (i = 1; i < size - 1; i++)
{
DA1[i] = DA1[i-1] + A[i];
}
// this second array is the counter part to the first one so for example
// for a set {1, 2, -1 } if DA1 got {1} covered, DA2 will cover {2, -1}
DA2[size-1] = A[size-1];
for (i = size - 2; i >= 0; i--)
{
DA2[i] = DA2[i + 1] + A[i];
}
// find the best combination
for (i = 0; i < size - 1; i++)
{
int temp = max(DA1[i].max - DA2[i].min, DA2[i].max - DA1[i].min);
if (temp > bestdiff)
bestdiff = temp;
}
return bestdiff;
}
int main (int argc, void** argv)
{
int A[] = {4,-1,7}; //{1, 2, 5, -15,5,-2, 1, 0};//{1, 2, -5, 10, 0, - 15, -1, 3, -4};
int size = sizeof(A)/sizeof(int);
cout<<maxdiffinsubsets(A, size)<<endl;
_getch();
}
string res;
void possibletext(char* input)
{
if (input == nullptr ||
input[0] == '\0')
{
cout<<res<<endl;
return;
}
// read first digit and print
if (input[0] >='1' && input[0] <='9' && input[1] != '0')
{
int num = (input[0] - '0') - 1;
res += ('a'+num);
possibletext(input+1);
res.pop_back();
}
// handle the special case where two digits can be combined
if (input[0] == '1' ||
(input[0] == '2' && input[1] >= '1' && input[1] <='6'))
{
int num = (input[0]-'0')*10 + (input[1]-'0') - 1;
res += (char)('a'+num);
possibletext(input+2);
res.pop_back();
}
}
int main(int argc, char** argv)
{
char* one = "1123";
possibletext(one);
_getch();
}
finished going through all the posts on here. :) Seems like my implementation is closest to what Loler suggested in C. Only difference is I am using two DA and each maintains structure that keeps track of max and min for the interval.
- sameep June 18, 2013