http://www.spoj.com/problems/GSS1/
Typical problem statement can be seen as below.
Problem: Given a array of numbers a[1...n] , and a query range [x,y].
query(x,y) should return the sub-sequence sum, whose sum is maximum in the interval [x,y].
Lets analyze this query.
Query(x,y) is the maximum of below values where sum(i,j) = a[i]+a[i+1]+......+a[j];
sum(x,x) |
sum(x,x+1) |
sum(x,x+2) |
.......... |
sum(x,y-1) |
sum(x,y) |
|
sum(x+1,x+1) |
sum(x+1,x+2) |
.......... |
sum(x+1,y-1) |
sum(x+1,y) |
|
|
sum(x+2,x+2) |
.......... |
sum(x+2,y-1) |
sum(x+2,y) |
|
|
|
.......... |
.......... |
.......... |
|
|
|
|
sum(y-1,y-1) |
sum(y-1,y) |
|
|
|
|
|
sum(y,y) |
Seriously whats wrong with coloring -we will come to that part.
Blue::The Color of Left Sum.
Where the range starts at 'x' but ends at any where in [x,y].
sum(x,x) |
sum(x,x+1) |
sum(x,x+2) |
.......... |
sum(x,y-1) |
sum(x,y) |
|
sum(x+1,x+1) |
sum(x+1,x+2) |
.......... |
sum(x+1,y-1) |
sum(x+1,y) |
|
|
sum(x+2,x+2) |
.......... |
sum(x+2,y-1) |
sum(x+2,y) |
|
|
|
.......... |
.......... |
.......... |
|
|
|
|
sum(y-1,y-1) |
sum(y-1,y) |
|
|
|
|
|
sum(y,y) |
Red::The Color of Right Sum.
Where the range starts at somewhere in [x,y] and ends at 'y'.
sum(x,x) |
sum(x,x+1) |
sum(x,x+2) |
.......... |
sum(x,y-1) |
sum(x,y) |
|
sum(x+1,x+1) |
sum(x+1,x+2) |
.......... |
sum(x+1,y-1) |
sum(x+1,y) |
|
|
sum(x+2,x+2) |
.......... |
sum(x+2,y-1) |
sum(x+2,y) |
|
|
|
.......... |
.......... |
.......... |
|
|
|
|
sum(y-1,y-1) |
sum(y-1,y) |
|
|
|
|
|
sum(y,y) |
Grey::The Color of Sum of the Elements.
Simply sum of all elements in interval [x,y].
sum(x,x) |
sum(x,x+1) |
sum(x,x+2) |
.......... |
sum(x,y-1) |
sum(x,y) |
|
sum(x+1,x+1) |
sum(x+1,x+2) |
.......... |
sum(x+1,y-1) |
sum(x+1,y) |
|
|
sum(x+2,x+2) |
.......... |
sum(x+2,y-1) |
sum(x+2,y) |
|
|
|
.......... |
.......... |
.......... |
|
|
|
|
sum(y-1,y-1) |
sum(y-1,y) |
|
|
|
|
|
sum(y,y) |
Green::The Color of nested Query ;).
Well, you can see this as the Query(x+1,y-1).
sum(x,x) |
sum(x,x+1) |
sum(x,x+2) |
.......... |
sum(x,y-1) |
sum(x,y) |
|
sum(x+1,x+1) |
sum(x+1,x+2) |
.......... |
sum(x+1,y-1) |
sum(x+1,y) |
|
|
sum(x+2,x+2) |
.......... |
sum(x+2,y-1) |
sum(x+2,y) |
|
|
|
.......... |
.......... |
.......... |
|
|
|
|
sum(y-1,y-1) |
sum(y-1,y) |
|
|
|
|
|
sum(y,y) |
Now, you can understand why i had to use these colors.
Lets maintain 4 values.
bestLeftSum - Best of all the Left Sums
bestRightSum - Best of all the Right Sums
Sum - Sum of all the elements
bestSum - well we need this to store resultSum of each query (Nested Query ;))
Logically, Query(x,y).resultSum = max (bestLeftSum,bestRightSum,sum,Query(x+1,y-1).bestSum);
But still the nested query stuff isn't so good O(N^2) :'(.
Why can't we use a tree(SegmentTree) ?? Why not a O(logN) for query??
Lets call the above info {bestLeftSum,bestRightSum,Sum,bestSum} as QueryNode.
and given information about QueryNode(L,M) and QueryNode(M+1,R).
Can't you be able to determine the QueryNode(L,R) with above information??
QueryNode(L,M) -> l
QueryNode(M+1,R) -> r
Then For QueryNode(L,R),
bestLeftSum = max (l.bestLeftSum,l.Sum+r.bestLeftSum);
bestRightSum = max (l.bestRightSum+r.Sum,r.bestRightSum);
Sum = l.Sum+r.Sum;
bestSum = max(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);
How?? - Check below graphical representation
Implementation of the Same - Solution
// =====================================================================================
// Filename: GSS1.cpp
// Description:
// Created: 05/23/2013 06:41:42 PM
// Author: BrOkEN@!
// =====================================================================================
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)
using namespace std;
typedef pair<int,int> PI;
typedef vector<PI> VI;
inline int max2(int a, int b) {return ((a > b)? a : b);}
inline int max3(int a, int b, int c) {return max2(a, max2(b, c));}
const int MAX = 1 << 16;
int a[MAX];
struct node
{
int Sum,bestLeftSum,bestRightSum,bestSum;
node split(node& l, node& r){
} // No Need of Split Function
node merge(node& l, node& r)
{
Sum = l.Sum + r.Sum;
bestLeftSum = max( l.Sum + r.bestLeftSum , l.bestLeftSum );
bestRightSum = max( r.Sum + l.bestRightSum , r.bestRightSum );
bestSum = max( max( l.bestSum , r.bestSum) , l.bestRightSum + r.bestLeftSum );
}
node setValue(int val){
Sum = bestLeftSum = bestRightSum = bestSum = val;
}
};
node T[MAX << 1];
void init(int Node, int i, int j) {
if(i==j) { // Initialize Leaf Nodes
T[Node].setValue(a[i]);
return;
}else{ // Summerize Descendant Nodes Nodes
int m = (i+j)/2;
init(2*Node, i, m);
init(2*Node+1, m+1, j);
T[Node].merge(T[2*Node],T[2*Node+1]);
}
}
void update(int Node, int i, int j,int idx, int val) {
// Update element with index 'idx' in the range [i,j]
if(i==j && i == idx) { // Update the LeafNode idx
T[Node].setValue(val);
return;
}else{ // Summerize Descendant Nodes Nodes
int m = (i+j)/2;
if(idx <=m)
update(2*Node, i, m, idx, val);
else
update(2*Node+1, m+1, j, idx, val);
T[Node].merge(T[2*Node],T[2*Node+1]);
}
}
void range_query(node& resultNode,int Node,int i, int j, int L, int R){ // Search for Node having interval info [L,R] in [i,j]; (i<=L<R<=j)
if(i==L && j==R){
resultNode = T[Node];
return;
}else{
int m = (i+j)/2;
if(R<=m)
range_query(resultNode, 2*Node, i, m, L, R);
else if(L>m)
range_query(resultNode, 2*Node+1, m+1, j, L, R);
else{
node left, right;
range_query(left, 2*Node, i, m, L, m);
range_query(right, 2*Node+1, m+1, j, m+1, R);
resultNode.merge(left,right);
}
}
}
int solve(){
return 0;
}
int main(){
int N=0,M=0;
node res;
scanf("%d",&N);
FOR(i,0,N-1){
scanf("%d", &a[i]);
}
init(1, 0, N-1);
scanf("%d",&M);
int x,y;
FOR(i,0,M-1){
scanf("%d%d",&x,&y);
range_query(res, 1, 0, N-1, --x, --y);
printf("%d\n", res.bestSum);
}
return 0;
}
Nice work
ReplyDeleteGreat Explanation...
ReplyDeleteExcellent Explaination bro !! God bless you..
ReplyDeletenice man
ReplyDeleteVery Good and Thank You ...:)
ReplyDeleteGreat work. Thanks for the explanation :)
ReplyDeleteawesome
ReplyDeleteBest explanation ever bro !!
ReplyDeleteaah
ReplyDelete_/\_
ReplyDelete