Tips in optimizing an algorithm

Question

I'll try to phrase this question without making it sound like I am seeking for homework answers (this is just a practice problem for algorithms)

you have an array of numbers where every value can occur at most 2x [1 3 5 2 5 1 2 3] Examine sums from one value to the other instance of itself (5 + 2 + 5) (2 + 5 + 1 + 2)

Find an algorithm that finds the max of such sum.

I came up with a pretty simple algorithm:

iterate through the array (for i=1 to n)
iterate through the remaining array (for j=i+1)
if A[i] == A[j]
    s = 0
    iterate through the values between those two points (for k=i to j)
        s = s + A[k]
    maxVal = max(maxVal,s)

What are some steps I can take towards optimizing the algorithm. (or any algorithm for that matter). Obviously this solution is the first that came to mind but I am having trouble envisioning better solutions that would be more efficient.

Edit: For sake of the problem I'll just say all elements are postitive

MBo · Accepted Answer · 2014-04-01 03:50:05Z

3

Calculate array of cumulative sums:

C[0] = A[0]  
for i = 1 to n  
  C[i] = C[i - 1] + A[i]  
A[1 3 5 2 5 1 2 3]  
C[0 1 4 9 11 16 17 19 22]

Use these values when pair found:

  Sum(i to j) = C[j] - C[i - 1]

P.S. Are all elements always positive?

answered Apr 1, 2014 at 3:50

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

CoderNinja Over a year ago

wow this is really smart! I really wish i had a knack for creative solutions like this. What were some of the first things you considered when trying to optimize my solution? (Trying to improve my optimization skills)

MBo Over a year ago

If you can use additional memory, look also at Pham Trung suggestion about hashmap/dusctionary

Niklas B. Over a year ago

@CoderNinja The reduction from infix aggregations to prefix aggregations is a well-known construction in algorithm engineering. Learning this stuff just takes a bit of practice. I can recommend platforms like TopCoder or Codeforces if you want to practice your algorithm/problem solving skills (but it takes effort, there's no free lunch and no simple tips that magically make you solve problems faster).

MBo Over a year ago

@CoderNinja You might notice that initial algorithm calculates almost similar sums (on slightly shifted intervals) again and again.

Pham Trung · Accepted Answer · 2014-04-01 04:05:10Z

2

You can get rid of the most inner loop by pre calculate all the sum from index 1 to index i and store it into an array, call sum. So if you want to get the sum between i and j, the result will be sum[j] - sum[i - 1].

for(i = 1 to n)
  sum[i] = A[i];
  if(i - 1 > 1)
    sum[i] += sum[i - 1];

Also notice that there are only two occurrences for each value in the array, we can remember the first position of this value using a map/dictionary or an array pos (if possible) and if we saw it again , we can use it to calculate the sum between the first and this position.

  pos[];
  for(i = 1 to n)
     if(pos[A[i]] ==0)
       pos[A[i]] = i;
     else
       result = max(result,sum[i] - sum[pos[A[i]] - 1])

So in total, the time complexity of this will be O(n)

edited Apr 1, 2014 at 4:05

answered Apr 1, 2014 at 3:54

Pham Trung

11.3k2 gold badges26 silver badges43 bronze badges

1 Comment

Niklas B. Over a year ago

expected O(n) ;) Or maybe even O(n) with high probability, depending on the hash table implementation

Collectives™ on Stack Overflow

Tips in optimizing an algorithm

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related