Algorithms : complete 01-algorithmic_toolbox 04-dynamic_programming

1 files changed, 87 insertions, 13 deletions

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
index 06861ab..8867a1e 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp
@@ -2,27 +2,101 @@
 #include <cassert>
 #include <string>
 #include <vector>
+#include <limits>
 
 using std::vector;
 using std::string;
 using std::max;
 using std::min;
 
-long long eval(long long a, long long b, char op) {
-  if (op == '*') {
-    return a * b;
-  } else if (op == '+') {
-    return a + b;
-  } else if (op == '-') {
-    return a - b;
-  } else {
-    assert(0);
-  }
+long long eval(long long a, long long b, char op)
+{
+    if (op == '*') {
+        return a * b;
+    } else if (op == '+') {
+        return a + b;
+    } else if (op == '-') {
+        return a - b;
+    } else {
+        assert(0);
+    }
 }
 
-long long get_maximum_value(const string &exp) {
-  //write your code here
-  return 0;
+void get_min_max(int n, int x, int i, int j, const string &ops, long long *mins, long long *maxs)
+{
+    long long min = std::numeric_limits<long long>::max();
+    long long max = std::numeric_limits<long long>::min();
+
+    for (int k = i; k < j; k++) {
+        int x = i * n + k;
+        int y = (k + 1) * n + j;
+        long long a = eval(maxs[x], maxs[y], ops[k]);
+        long long b = eval(maxs[x], mins[y], ops[k]);
+        long long c = eval(mins[x], mins[y], ops[k]);
+        long long d = eval(mins[x], maxs[y], ops[k]);
+        if (a < min) min = a;
+        if (b < min) min = b;
+        if (c < min) min = c;
+        if (d < min) min = d;
+        if (a > max) max = a;
+        if (b > max) max = b;
+        if (c > max) max = c;
+        if (d > max) max = d;
+    }
+    mins[x] = min;
+    maxs[x] = max;
+}
+
+long long get_maximum_value(const string &exp)
+{
+    int n = (exp.length() + 1) / 2;
+    int nn = (n * n);
+
+    string ops;
+    long long *mins = new long long[nn];
+    long long *maxs = new long long[nn];
+
+    // collect the operators
+    for (int i = 1; i < exp.length(); i+=2)
+        ops += exp[i];
+
+    // feed both diagonals with operands
+    for (int i = 0, k = 0; i < nn; i+=(n + 1), k+=2)
+        maxs[i] = mins[i] = (exp[k] - '0');
+
+    // feed both first diagonals, result of pair
+    for (int i = 1, k = 1; i < nn; i+=(n + 1), k+=2)
+        maxs[i] = mins[i] = eval(mins[i - 1], mins[i + n], exp[k]);
+
+    for (int i = 2, k = (n - 2); i < n; i++, k-=1) {
+        for (int j = 0; j < k; j++) {
+            int x = i + j * (n + 1);
+            /* maxs[x] = mins[x] = k; */
+            /* std::cout << "[" << j <<";"<< j + i<<"]"<< std::endl; */
+            get_min_max(n, x, j, j + i, ops, mins, maxs);
+        }
+    }
+
+    /* std::cout << std::endl; */
+    /* for (int i = 0; i < nn; i+=n) { */
+    /* 	for (int j = 0; j < n; j++) */
+    /* 		std::cout << mins[i + j] << " "; */
+    /* 	std::cout << std::endl; */
+    /* } */
+    /* std::cout << std::endl; */
+    /* for (int i = 0; i < nn; i+=n) { */
+    /* 	for (int j = 0; j < n; j++) */
+    /* 		std::cout << maxs[i + j] << " "; */
+    /* 	std::cout << std::endl; */
+    /* } */
+    /* std::cout << std::endl; */
+
+    long long ret = maxs[n - 1];
+
+    delete [] mins;
+    delete [] maxs;
+
+    return ret;
 }
 
 int main() {