summaryrefslogtreecommitdiff
path: root/16_subseq
diff options
context:
space:
mode:
Diffstat (limited to '16_subseq')
-rw-r--r--16_subseq/.gitignore2
-rw-r--r--16_subseq/README34
-rw-r--r--16_subseq/grade.txt17
-rw-r--r--16_subseq/maxSeq.c71
4 files changed, 124 insertions, 0 deletions
diff --git a/16_subseq/.gitignore b/16_subseq/.gitignore
new file mode 100644
index 0000000..f721019
--- /dev/null
+++ b/16_subseq/.gitignore
@@ -0,0 +1,2 @@
+maxSeq
+Makefile
diff --git a/16_subseq/README b/16_subseq/README
new file mode 100644
index 0000000..9966603
--- /dev/null
+++ b/16_subseq/README
@@ -0,0 +1,34 @@
+
+ 1. Create a file called maxSeq.c and write the function:
+ size_t maxSeq(int * array, size_t n);
+
+ which returns the length of the maximum increasing contiguous
+ subsequence in the array. The parameter n specifies the length
+ of the array For example, if the array passed in were
+
+ { 1, 2, 1, 3, 5, 7, 2, 4, 6, 9}
+
+ this function would return 4 because the longest sequence
+ of (strictly) increasing numbers in that array is 1, 3, 5, 7
+ which has length 4. Note that 1,3,5,7,9 is an increasing
+ subsequence, but is not contiguous (finding discontiguous
+ ones efficiently takes techniques we haven't learned yet).
+
+ Note that the subseqence does not need to increase at a
+ constant rate (or follow any other pattern besides being strictly
+ increasing). 2, 4, 67, 93, 94, 102 would be a valid increasing
+ sequence of length 6.
+
+ Also note that the series consisting of one element is considered an
+ increasing sequence of length 1.
+
+
+2. Compile and test your code using the test-subseq.c you wrote
+ previously. (as before, compile the .c files separately, and link
+ them together).
+
+3. Submit your code for maxSeq.c
+
+
+Hint:
+ Can you abstract a complex step out into a simple function?
diff --git a/16_subseq/grade.txt b/16_subseq/grade.txt
new file mode 100644
index 0000000..05a9ca8
--- /dev/null
+++ b/16_subseq/grade.txt
@@ -0,0 +1,17 @@
+Grading at Thu 14 Oct 2021 09:19:34 PM UTC
+Attempting to compile maxSeq.c
+Linking your object file with our test main
+#################################################
+testcase2:
+array size:0 was Correct
+#################################################
+testcase3:
+array size:1 was Correct
+#################################################
+testcase4:
+array size:100 was Correct
+#################################################
+testcase5:
+array size:5000 was Correct
+
+Overall Grade: A
diff --git a/16_subseq/maxSeq.c b/16_subseq/maxSeq.c
new file mode 100644
index 0000000..da03171
--- /dev/null
+++ b/16_subseq/maxSeq.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+size_t maxSeq(int * array, size_t n) {
+ if (n == 0) {
+ return 0;
+ }
+ size_t longest_streak_length = 1;
+ size_t running_streak_length = 1;
+ int temp = array[0];
+
+ for (size_t i = 1; i < n; i++) {
+ if (array[i] > temp) {
+ running_streak_length++;
+ if (running_streak_length > longest_streak_length) {
+ longest_streak_length = running_streak_length;
+ }
+ } else {
+ running_streak_length = 1;
+ }
+ temp = array[i];
+ }
+ return longest_streak_length;
+
+}
+
+
+//int main(void) {
+// if (maxSeq(NULL, 0)) {
+// return EXIT_FAILURE;
+// }
+//
+// int array1[] = {1, 2, 3, 2};
+// int array2[] = {2, -3, 5, 6, 8};
+// int array3[] = {5};
+// int array4[] = {2, 4, 3, 6, 10, 15, -1, 7, 8, 2};
+// int array5[] = {-2};
+// int array6[] = {2,2,2,3};
+//
+// if (maxSeq(array1, 0)) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array1, 4) != 3) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array2, 5) != 4) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array3, 1) != 1) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array4, 10) != 4) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array5, 1) != 1) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+// if (maxSeq(array6, 4) != 2) {
+// printf("not good!\n");
+// return EXIT_FAILURE;
+// }
+//
+// printf("good!\n");
+// return EXIT_SUCCESS;
+//}