aboutsummaryrefslogtreecommitdiff
path: root/integer_break.c
diff options
context:
space:
mode:
Diffstat (limited to 'integer_break.c')
-rw-r--r--integer_break.c37
1 files changed, 37 insertions, 0 deletions
diff --git a/integer_break.c b/integer_break.c
new file mode 100644
index 0000000..27ad29e
--- /dev/null
+++ b/integer_break.c
@@ -0,0 +1,37 @@
+// 343. Integer Break
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * given an integer 'n', break it into the sum of 'k' positive integers, where
+ * 'k >= 2' and maximise the product of those integers. return the maximum
+ * product you can get
+ */
+
+int integerBreak(int n) {
+ int *dp = (int *)malloc((n + 1) * sizeof(int));
+ dp[0] = 0;
+ dp[1] = 1;
+ dp[2] = 1;
+ int max = INT_MIN, half, val, a, b;
+ for (int i = 3; i <= n; i++) {
+ half = i / 2;
+ for (int j = 1; j <= half; j++) {
+ a = (dp[j] > j) ? dp[j] : j;
+ b = (dp[i - j] > (i - j)) ? dp[i - j] : (i - j);
+ val = a * b;
+ if (val > max)
+ max = val;
+ }
+ dp[i] = max;
+ }
+ int ans = dp[n];
+ free(dp);
+ return ans;
+}
+
+int main() {
+ printf("%d\n", integerBreak(2)); // expect: 1 (2 = 1 + 1, 1 * 1 = 1)
+ printf("%d\n", integerBreak(10)); // expect: 36 (10 = 3 + 3 + 4, 3 * 3 * 4)
+}