Find maximun range of an array
-
Greetings, i have a problem finding a solution for this algorithm: i have to find the maximun range in an unordered array (i cant order the array). An example will be: +--------------------------+ | 100 | -10 | -10 | -10 | 100 | --> this sould return the range 0-4 +--------------------------+ +-----------------+ | -7 | 5 | -1 | 9 | -6 | --> this sould return the range 1-3 +-----------------+ +-----------------+ | -7 | 5 | -6 | 9 | -6 | --> this sould return the range 3-3 +-----------------+ I dont have problems doing the algorithm in O(n^2) but i need to do this algoithm in O(n), can anyone help me? Cuadratic algorithm:
void maximunSegment(vector &V, int &start, int &end){
int i = 0, j = 0, r = 0, aux = 0;
start = 0; end = 0;while(i < V.size()){ j = i; while(j < V.size() - 1){ aux += V\[j\]; if(aux >= r){ r = aux; start = i + 1; end = j + 1; } ++j; } aux = 0; ++i; }}
IMPORTANTE NOTE: the positions of the array are important, i mean that the content of V[i] is linked to that i (if v[3] = 89, that 89 always have to refered to v[3] even if you change the array you need to remember that this 89 was on position 3), so if you reorder the array you need to keep that reference. Thank you so much.
-
Greetings, i have a problem finding a solution for this algorithm: i have to find the maximun range in an unordered array (i cant order the array). An example will be: +--------------------------+ | 100 | -10 | -10 | -10 | 100 | --> this sould return the range 0-4 +--------------------------+ +-----------------+ | -7 | 5 | -1 | 9 | -6 | --> this sould return the range 1-3 +-----------------+ +-----------------+ | -7 | 5 | -6 | 9 | -6 | --> this sould return the range 3-3 +-----------------+ I dont have problems doing the algorithm in O(n^2) but i need to do this algoithm in O(n), can anyone help me? Cuadratic algorithm:
void maximunSegment(vector &V, int &start, int &end){
int i = 0, j = 0, r = 0, aux = 0;
start = 0; end = 0;while(i < V.size()){ j = i; while(j < V.size() - 1){ aux += V\[j\]; if(aux >= r){ r = aux; start = i + 1; end = j + 1; } ++j; } aux = 0; ++i; }}
IMPORTANTE NOTE: the positions of the array are important, i mean that the content of V[i] is linked to that i (if v[3] = 89, that 89 always have to refered to v[3] even if you change the array you need to remember that this 89 was on position 3), so if you reorder the array you need to keep that reference. Thank you so much.
Member 13501021 wrote:
...i have to find the maximun range
When I hear the phrase "maximum range" I think of things like: 1) what's the farthest that ball can be hit, 2) what's the longest distance that bullet will travel in 50% humidity, 3) what's the farthest that car can go on a full tank. What is your definition of maximum range?
Member 13501021 wrote:
+--------------------------+ | 100 | -10 | -10 | -10 | 100 | --> this sould return the range 0-4 +--------------------------+ +-----------------+ | -7 | 5 | -1 | 9 | -6 | --> this sould return the range 1-3 +-----------------+ +-----------------+ | -7 | 5 | -6 | 9 | -6 | --> this sould return the range 3-3
What's the pattern?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
Member 13501021 wrote:
...i have to find the maximun range
When I hear the phrase "maximum range" I think of things like: 1) what's the farthest that ball can be hit, 2) what's the longest distance that bullet will travel in 50% humidity, 3) what's the farthest that car can go on a full tank. What is your definition of maximum range?
Member 13501021 wrote:
+--------------------------+ | 100 | -10 | -10 | -10 | 100 | --> this sould return the range 0-4 +--------------------------+ +-----------------+ | -7 | 5 | -1 | 9 | -6 | --> this sould return the range 1-3 +-----------------+ +-----------------+ | -7 | 5 | -6 | 9 | -6 | --> this sould return the range 3-3
What's the pattern?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
Pretty sure that the "maximum range" should be the segment of the array where the sum of its values is the highest of all possible segments.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
-
Greetings, i have a problem finding a solution for this algorithm: i have to find the maximun range in an unordered array (i cant order the array). An example will be: +--------------------------+ | 100 | -10 | -10 | -10 | 100 | --> this sould return the range 0-4 +--------------------------+ +-----------------+ | -7 | 5 | -1 | 9 | -6 | --> this sould return the range 1-3 +-----------------+ +-----------------+ | -7 | 5 | -6 | 9 | -6 | --> this sould return the range 3-3 +-----------------+ I dont have problems doing the algorithm in O(n^2) but i need to do this algoithm in O(n), can anyone help me? Cuadratic algorithm:
void maximunSegment(vector &V, int &start, int &end){
int i = 0, j = 0, r = 0, aux = 0;
start = 0; end = 0;while(i < V.size()){ j = i; while(j < V.size() - 1){ aux += V\[j\]; if(aux >= r){ r = aux; start = i + 1; end = j + 1; } ++j; } aux = 0; ++i; }}
IMPORTANTE NOTE: the positions of the array are important, i mean that the content of V[i] is linked to that i (if v[3] = 89, that 89 always have to refered to v[3] even if you change the array you need to remember that this 89 was on position 3), so if you reorder the array you need to keep that reference. Thank you so much.
This surely is your homework, so I won't rob you of the opportunity to find the solution yourself. But I'll try to nudge you onto the right track: - Take a pen and paper, write down some random value sequences as input arrays and solve them manually. Try to do this in an algorithmic way. Use some longer sequences than you showed here. - You can't have nested loops over n for O(n), obviously. So you will have to make do with one pass over the array. But you're free to use more or other variables. - The solution is surprisingly easy and succinct - don't think too complicated.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson