diff options
Diffstat (limited to 'longest_arithmetic_subseq.c')
-rw-r--r-- | longest_arithmetic_subseq.c | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/longest_arithmetic_subseq.c b/longest_arithmetic_subseq.c new file mode 100644 index 0000000..56dec29 --- /dev/null +++ b/longest_arithmetic_subseq.c @@ -0,0 +1,44 @@ +// 1027. Longest Arithmetic Subsequence +#include <stdio.h> +#include <string.h> + +/* + * given an array 'nums' of integers, return the length of the longest + * arithmetic subsequence in 'nums'. note that + * - a subsequence is an array that can be derived from another array by + * deleting some or no elements without changing the order of the remaining + * elements. + * - a sequence 'seq' is arithmetic if 'seq[i + 1] - seq[i]' are all the same + * value (for '0 <= i < seq.len() - 1') + */ + +int longestArithSeqLength(int *nums, int nums_size) { + if (!nums) + return 0; + int min = nums[0], max = min; + for (int i = 0; i < nums_size; i++) { + if (nums[i] < min) + min = nums[i]; + if (nums[i] > max) + max = nums[i]; + } + int tmp = max - min, map[nums_size][2 * tmp + 1], ans = 0; + memset(map, 0, sizeof(map[0][0]) * nums_size * (2 * tmp + 1)); + for (int i = 0; i < nums_size; i++) + for (int j = 0; j < i; j++) { + int diff = nums[i] - nums[j] + tmp; + map[i][diff] = map[j][diff] + 1; + if (map[i][diff] > ans) + ans = map[i][diff]; + } + return ans + 1; +} + +int main() { + int n1[] = {3, 6, 9, 12}, ns1 = 4; + int n2[] = {9, 4, 7, 2, 10}, ns2 = 5; + int n3[] = {20, 1, 15, 3, 10, 5, 8}, ns3 = 7; + printf("%d\n", longestArithSeqLength(n1, ns1)); // expect: 4 + printf("%d\n", longestArithSeqLength(n2, ns2)); // expect: 3 + printf("%d\n", longestArithSeqLength(n3, ns3)); // expect: 4 +} |