Page **1** of **1**

### 11654 - Arithmetic Subsequence

Posted: **Wed Aug 26, 2009 6:43 pm**

by **Igor9669**

Hi!

I solved this problem, but my runtime is very large(1.040 sec). I'm interesting in your solutions, what method do you use and what is the complexity of your algo? My algo is - O(n^3 logN).

### Re: 11654 - Arithmetic Subsequence

Posted: **Thu Aug 27, 2009 1:38 pm**

by **crip121**

my run time complexity is N^3. its a pretty straight forward DP problem.

### Re: 11654 - Arithmetic Subsequence

Posted: **Thu Aug 27, 2009 4:44 pm**

by **Chimed**

Igor9669 wrote:Hi!

I solved this problem, but my runtime is very large(1.040 sec). I'm interesting in your solutions, what method do you use and what is the complexity of your algo? My algo is - O(n^3 logN).

Same as yours got 0.364sec.

### Re: 11654 - Arithmetic Subsequence

Posted: **Thu Aug 27, 2009 7:12 pm**

by **Igor9669**

Chimed wrote:Same as yours got 0.364sec.

Do you use stl in your solution?

### Re: 11654 - Arithmetic Subsequence

Posted: **Thu Aug 27, 2009 7:15 pm**

by **Igor9669**

crip121 wrote:my run time complexity is N^3. its a pretty straight forward DP problem.

Could you explain it?

### Re: 11654 - Arithmetic Subsequence

Posted: **Fri Aug 28, 2009 11:42 am**

by **Khongor_SMCS**

Let a*[j] = Number of arithmetic subset using number 1 to j and last two number is i'th and j'th.*

O(N^3)

### Re: Hi14

Posted: **Sat Oct 17, 2009 3:37 pm**

by **arifcsecu**