From fc245a6f71f57f5131d46c62cd42929968689e4b Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 3 Oct 2018 21:58:31 -0500
Subject: Largest number aka maximize salary done!

---
 PlaygroundCpp/Sources/Playground.cpp | 99 +++++++++++++++++++++++++++---------
 1 file changed, 74 insertions(+), 25 deletions(-)

(limited to 'PlaygroundCpp/Sources')

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 6892515..6b9efff 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,38 +1,87 @@
+#include <algorithm>
+#include <sstream>
 #include <iostream>
 #include <vector>
+#include <string>
 //#include <gtest/gtest.h>
 
 using std::vector;
+using std::string;
 
-vector<int> optimal_summands(int n) {
-	vector<int> summands;
-	if (n < 3) {
-		summands.push_back(n);
-		return summands;
-	}
-	int runningSum = 0;
-	for (int i = 1; i < n + 1; i++) {
-		runningSum = runningSum + i;
-		summands.push_back(i);
-		if (runningSum == n) {
-			break;
-		}
-		if (runningSum > n) {
-			summands.pop_back();
-			summands.back() = summands.back() + n - runningSum + i;
-			break;
+bool compare_leading_digits(string s1, string s2) {
+	return stoi(s1 + s2) > stoi(s2 + s1);
+}
+
+static string largest_number(vector<string> a) {
+	string result = "";
+	string maxDigit = "0";
+	int indexHolder = 0;
+	while (a.size() > 0){
+		for (int i = 0; i< a.size(); i++) {
+			if (compare_leading_digits(a[i], maxDigit)) {
+				maxDigit = a[i];
+				indexHolder = i;
+			}
 		}
+		result = result + maxDigit;
+		maxDigit = "0";
+		a.erase(a.begin()+indexHolder);
 	}
-	return summands;
+	return result;
 }
 
+//TEST(CompareLeadingDigits, CompareTest1) {
+//	ASSERT_TRUE(compare_leading_digits("2", "21"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest2) {
+//	ASSERT_FALSE(compare_leading_digits("20", "21"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest3) {
+//	ASSERT_FALSE(compare_leading_digits("321", "322"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest4) {
+//	ASSERT_FALSE(compare_leading_digits("321", "32"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest5) {
+//	ASSERT_FALSE(compare_leading_digits("10", "1"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest6) {
+//	ASSERT_TRUE(compare_leading_digits("6", "10"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest7) {
+//	ASSERT_TRUE(compare_leading_digits("23", "2"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest8) {
+//	ASSERT_TRUE(compare_leading_digits("545", "54"));
+//}
+//
+//TEST(CompareLeadingDigits, CompareTest9) {
+//	ASSERT_TRUE(compare_leading_digits("56", "565"));
+//}
+//
+//TEST(LargestNumber, LargestTest1) {
+//	vector<string> nums = {"9", "4", "6", "1", "9"};
+//	ASSERT_EQ("99641", largest_number(nums));
+//}
+//
+//TEST(LargestNumber, LargestTest2) {
+//	vector<string> nums = {"21", "2"};
+//	ASSERT_EQ("221", largest_number(nums));
+//}
 
 int main() {
-	int n;
-	std::cin >> n;
-	vector<int> summands = optimal_summands(n);
-	std::cout << summands.size() << '\n';
-	for (size_t i = 0; i < summands.size(); ++i) {
-		std::cout << summands[i] << ' ';
-	}
+  int n;
+  std::cin >> n;
+  vector<string> a(n);
+  for (size_t i = 0; i < a.size(); i++) {
+    std::cin >> a[i];
+  }
+  std::cout << largest_number(a);
 }
-- 
cgit v1.2.3