1 files changed, 94 insertions, 56 deletions

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 3083cdc..dd6d90b 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,77 +1,115 @@
 #include <iostream>
 #include <vector>
+#include <climits>
+#include <cassert>
 //#include <gtest/gtest.h>
 
 using std::vector;
+using std::string;
+using std::max;
+using std::min;
 
-vector<vector<int>> optimalWeight2DArray(int W, vector<int> &w2) {
-	int j = w2.size();
-//	int value[W + 1][j + 1];
-	vector<vector<int> > value(W + 1, vector<int>(j + 1));
+long eval(long a, long b, char op) {
+	if (op == '*') {
+		return a * b;
+	} else if (op == '+') {
+		return a + b;
+	} else if (op == '-') {
+		return a - b;
+	} else {
+		assert(0);
+	}
+}
 
-	for (int i = 0; i < j + 1; i++) {
-		for (int w = 0; w < W + 1; w++) {
-			if (i == 0 || w == 0) {
-				value[w][i] = 0;
-				continue;
-			}
-			value[w][i] = value[w][i - 1];
-			if (w2[i - 1] <= w) {
-				int val = value[w - w2[i - 1]][i - 1] + w2[i - 1];
-				if (value[w][i] < val) {
-					value[w][i] = val;
-				}
-			}
-		}
+vector<long> minAndMax(vector<vector<long>> &m, vector<vector<long>> &M,
+		vector<char> &op, int i, int j) {
+	long minValue = LONG_MAX;
+	long maxValue = LONG_MIN;
+	vector<long> result;
 
+	for (int k = i; k < j; k++) {
+		long a = eval(M[i][k], M[k + 1][j], op[k]);
+		long b = eval(M[i][k], m[k + 1][j], op[k]);
+		long c = eval(m[i][k], M[k + 1][j], op[k]);
+		long d = eval(m[i][k], m[k + 1][j], op[k]);
+		minValue = min(minValue, min(a, min(b, min(c, d))));
+		maxValue = max(maxValue, max(a, max(b, max(c, d))));
 	}
-	return value;
+	result.push_back(minValue);
+	result.push_back(maxValue);
+	return result;
 }
-
-int partition3(vector<int> &a) {
-	if (a.size() < 3)
-		return 0;
-	int sum = 0;
-	for (int i = 0; i < a.size(); i++) {
-		sum = sum + a[i];
+long getMaxValue(vector<int> &d, vector<char> &op) {
+	vector<vector<long>> m(d.size(), vector<long>(d.size()));
+	vector<vector<long>> M(d.size(), vector<long>(d.size()));
+	for (int i = 0; i < d.size(); i++) {
+		m[i][i] = d[i];
+		M[i][i] = d[i];
 	}
-	if (sum % 3 != 0)
-		return 0;
-	int W = sum / 3;
-	vector<vector<int> > values = optimalWeight2DArray(W, a);
-	int count = 0;
-	for (int i = 1; i < a.size() + 1; i++) {
-		for (int w = 1; w < W + 1; w++) {
-			if (values[w][i] == W)
-				count = count + 1;
+	for (int s = 0; s < op.size(); s++) {
+		for (int i = 0; i < d.size() - s; i++) {
+			int j = i + s + 1;
+			if (j >= d.size())
+				break;
+			vector<long> tempMinAndMax = minAndMax(m, M, op, i, j);
+			m[i][j] = tempMinAndMax[0];
+			M[i][j] = tempMinAndMax[1];
 		}
 	}
-	if (count >= 3)
-		return 1;
-	else
-		return 0;
+	return M[0][d.size() - 1];
+}
+
+long getMaxValue(string exp) {
+	int x = exp.length();
+	vector<int> d;
+	vector<char> op;
+
+	for (int i = 0; i < x - 1; i = i + 2) {
+		d.push_back(exp[i] - '0');
+		op.push_back(exp[i + 1]);
+	}
+	d.push_back(exp[x - 1] - '0');
+	return getMaxValue(d, op);
 }
-//TEST(KnapsackPartition3, t1) {
-//	vector<int> a = { 3, 3, 3, 3 };
-//	ASSERT_EQ(0, partition3(a));
+
+//vector<int> parseExp(string exp) {
+//	int x = exp.length();
+//	vector<int> d;
+//	vector<char> op;
+//
+//	for (int i = 0; i < x - 1; i = i + 2) {
+//		d.push_back(exp[i] - '0');
+//		op.push_back(exp[i + 1]);
+//	}
+//	d.push_back(exp[x - 1] - '0');
+//	return d;
+////	return getMaxValue(d, op);
 //}
 //
-//TEST(KnapsackPartition3, t2) {
-//	vector<int> a = { 30 };
-//	ASSERT_EQ(0, partition3(a));
+//TEST(MaxExpValue, t1) {
+//	string exp = "1+5";
+//	ASSERT_EQ(6, getMaxValue(exp));
 //}
 //
-//TEST(KnapsackPartition3, t3) {
-//	vector<int> a = { 1, 2, 3, 4, 5, 5, 7, 7, 8, 10, 12, 19, 25 };
-//	ASSERT_EQ(1, partition3(a));
+//TEST(MaxExpValue, t2) {
+//	string exp = "5-8+7*4-8+9";
+//	ASSERT_EQ(200, getMaxValue(exp));
+//}
+//TEST(MaxExpValue, t3) {
+//	string exp = "1+2-3*4-5";
+//	ASSERT_EQ(6, getMaxValue(exp));
+//}
+//TEST(MaxExpValue, t4) {
+//	string exp = "1+2*3";
+//	ASSERT_EQ(9, getMaxValue(exp));
+//}
+//
+//TEST(ParseExpTest, t1) {
+//	string exp = "1+5";
+//	ASSERT_EQ(1, parseExp(exp)[0]);
 //}
-
 int main() {
-	int n;
-	std::cin >> n;
-	vector<int> A(n);
-	for (size_t i = 0; i < A.size(); ++i) {
-		std::cin >> A[i];
-	}
-	std::cout << partition3(A) << '\n';
+	string s;
+	std::cin >> s;
+	std::cout << getMaxValue(s) << '\n';
 }