1005 codes updated.

liuyubobobo · liuyubobobo · commit 282a6468da20 · 2019-03-09T21:17:58.000-08:00
diff --git a/1005-Maximize-Sum-Of-Array-After-K-Negations/cpp-1005/main.cpp b/1005-Maximize-Sum-Of-Array-After-K-Negations/cpp-1005/main.cpp
@@ -1,27 +1,48 @@
+/// Source : https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/
+/// Author : liuyubobobo
+/// Time   : 2019-03-09
+
 #include <iostream>
 #include <vector>
+#include <numeric>
 
 using namespace std;
 
 
+/// Sorting and Greedy
+/// Time Complexity: O(nlogn)
+/// Space Complexity: O(1)
 class Solution {
 public:
-    int findJudge(int N, vector<vector<int>>& trust) {
+    int largestSumAfterKNegations(vector<int>& A, int K) {
+
+        sort(A.begin(), A.end());
+
+        int neg = 0;
+        bool hasZero = false;
+        for(int i = 0; i < A.size(); i ++)
+            if(A[i] < 0) neg ++;
+            else if(A[i] == 0) hasZero = true;
 
-        vector<int> indegrees(N, 0), outdegrees(N, 0);
-        for(const vector<int>& e: trust)
-            outdegrees[e[0] - 1] ++,
-            indegrees[e[1] - 1] ++;
+        int t = min(neg, K);
+        for(int i = 0; i < t; i ++)
+            A[i] = -A[i];
+        K -= t;
 
-        for(int i = 0; i < N; i ++)
-            if(indegrees[i] == N - 1 && outdegrees[i] == 0)
-                return i + 1;
-        return -1;
+        if(K && !hasZero && K % 2){
+            sort(A.begin(), A.end());
+            A[0] = -A[0];
+        }
+
+        return accumulate(A.begin(), A.end(), 0);
     }
 };
 
 
 int main() {
 
+    vector<int> A1 = {4, 2, 3};
+    cout << Solution().largestSumAfterKNegations(A1, 1) << endl;
+
     return 0;
 }
