C++

Forum

 
A faster algorithm

szyfuch (8)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include<iostream>
using namespace std;

int main(){
    int n, *tab;
    long long int cur = 0, max = 0;
    cin>>n;
    tab = new int[n];
    for(long int i=0; i<n; i++)
                 cin>>tab[i];
    
    cur = 0, max = 0;
    for (int i = 0; i < n; i++) {
        cur = cur > -tab[i] ? cur + tab[i] : 0;
        max = max > cur ? max : cur;
    }
    cout<<max<<endl;
    return 0;
}


The algorithm have O(n). Is someone who know a faster algorithm?
Last edited on
ne555 (10692)
¿what is the algorithm supposed to do?
James Burnby (24)
You could calculate the values as they are inputted.
Syuf (117)
There are special RSQ, RMQ algorithms, which can calculate sum or min/max using only O(log(n)), but the building of the tree for it uses O(n). They are to be used when there are many queries.
szyfuch (8)
Thank you for answers. How to get O(log(n))?
Syuf (117)
Try to find in Google or somewhere else query "Range Sum Query", because it's very hard to explain this algorithm in written form. I can only give you some code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;


const int size = 131072, infinity = 2000000000;

struct MinMax
{
	int min_value, max_value;

	explicit MinMax(int min_v = infinity, int max_v = -infinity)
		: min_value(min_v), max_value(max_v) {}

	int diff()
	{ return max_value - min_value; }

} tree[2 * size + 100] = {};


void build_tree();
void update(int i, int newval);
MinMax find(int left, int right);


int main()
{
	for(int i = 1, next; i <= size; i++)
	{
		cin >> next;
		tree[i + size - 1] = MinMax(next, next);
	}
	build_tree();

	int queries_n;
	cin >> queries_n;
	for(int first, second; queries_n > 0; queries_n--)
	{
		cin >> first >> second;
                cout << find(first, second).diff() << endl;
	}

	return 0;
}


void build_tree()
{
	for(int i = size - 1; i >= 1; i--)
		tree[i] = MinMax(min(tree[2 * i].min_value, tree[2 * i + 1].min_value),
						 max(tree[2 * i].max_value, tree[2 * i + 1].max_value));
}

void update(int i, int newval)
{
	int v = i + size - 1;
	tree[v] = MinMax(newval, newval);
	v /= 2;
	while(v > 0)
	{
		tree[v] = MinMax(min(tree[2 * v].min_value, tree[2 * v + 1].min_value),
						 max(tree[2 * v].max_value, tree[2 * v + 1].max_value));
		v /= 2;
	}
}

MinMax find(int left, int right)
{
	left += size - 1;
	right += size - 1;
	MinMax result;

	while(left <= right)
	{
		if(left % 2)
		{
			result = MinMax(min(result.min_value, tree[left].min_value),
							max(result.max_value, tree[left].max_value));
			left++;
		}
		if(right % 2 == 0)
		{
			result = MinMax(min(result.min_value, tree[right].min_value),
							max(result.max_value, tree[right].max_value));
			right--;
		}
		left /= 2;
		right /= 2;
	}
	return result;
}
szyfuch (8)
What is the algorithm common with that I have written in my first post?
Last edited on
Syuf (117)
What is the algorithm common with that I have written in my first post?
No common. You need it?
Topic archived. No new replies allowed.