aboutsummaryrefslogtreecommitdiff
path: root/max_points_from_cards.c
diff options
context:
space:
mode:
Diffstat (limited to 'max_points_from_cards.c')
-rw-r--r--max_points_from_cards.c38
1 files changed, 38 insertions, 0 deletions
diff --git a/max_points_from_cards.c b/max_points_from_cards.c
new file mode 100644
index 0000000..19b711e
--- /dev/null
+++ b/max_points_from_cards.c
@@ -0,0 +1,38 @@
+// 1423. Maximum Points You Can Obtain from Cards
+#include <limits.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * there are several cards arranged in a row, and each card has an associated
+ * number of points. the points are given in the integer array 'card_points'. in
+ * one step you can take one card from the begining or from the end of the row.
+ * you have to take exactly 'k' cards. your score is the sum of the points of
+ * the cards you have taken. given the integer array 'card_points' and the
+ * integer 'k', return the maximum score you can obtain
+ */
+
+int maxScore(int *card_points, int card_points_size, int k) {
+ int n = card_points_size;
+ int *prefix = malloc((k + 1) * sizeof(int));
+ int *suffix = malloc((k + 1) * sizeof(int));
+ prefix[0] = 0;
+ suffix[0] = 0;
+ for (int i = 1; i <= k; i++) {
+ prefix[i] = prefix[i - 1] + card_points[i - 1];
+ prefix[i] = suffix[i - 1] + card_points[n - 1];
+ }
+ int max = INT_MIN;
+ for (int i = 0; i <= k; i++)
+ max = fmax(max, prefix[i] + suffix[k - i]);
+ return max;
+}
+
+int main() {
+ int cp1[] = {1, 2, 3, 4, 5, 6, 1}, cp2[] = {2, 2, 2},
+ cp3[] = {9, 7, 7, 9, 7, 7, 9};
+ printf("%d\n", maxScore(cp1, 7, 3)); // expect: 12
+ printf("%d\n", maxScore(cp2, 3, 2)); // expect: 4
+ printf("%d\n", maxScore(cp3, 7, 7)); // expect: 55
+}