leetcode

commit 46a123fde49ea184b1b83c2bf4e9c9b75618c2d5
parent dc0ba7d316475b058f66fa9acffbab813cbe0cc4
Author: AndrewLockVI <andrew.laack@gmail.com>
Date:   Wed,  5 Apr 2023 02:46:00 -0500

Completed Maximum subarray with C++

Diffstat:
A
maximum-subarray/a.out
 | 
0

A
maximum-subarray/maximum-subarray.cpp
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
A
maximum-subarray/maximum-subarrayV2.cpp
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 100 insertions(+), 0 deletions(-)
diff --git a/maximum-subarray/a.out b/maximum-subarray/a.out
Binary files differ.
diff --git a/maximum-subarray/maximum-subarray.cpp b/maximum-subarray/maximum-subarray.cpp
@@ -0,0 +1,46 @@
+#include <vector>
+#include <iostream>
+using namespace std;
+
+
+//Leet Ratings
+//       Speed  Memory
+//Total  168ms  67.6MB    
+//Beats  5.80%  93.55%
+
+
+int maxSubArray(vector<int>& nums) {
+
+    int size = nums.size();
+    int i = 0;
+    long int current_val = 0;
+    long int highest = nums[0];
+    while(i < size){
+        current_val = nums[i];
+
+        //This is necessary in case the final value of a list is the highest value.
+        if(current_val > highest){
+            highest = current_val;
+        }
+        int x = i + 1;
+        while(x < size & current_val > 0){
+            current_val += nums[x];
+            if(current_val > highest){
+                highest = current_val;
+            }
+            x += 1;
+        }
+        if(x == size){
+            break;
+        }
+
+        i += 1;
+        current_val = 0;
+    }
+    return highest;
+} 
+
+int main(){
+        vector<int> vector = {10, -1, -10, 32, 3, -3};
+        cout << maxSubArray(vector) << endl;
+}
diff --git a/maximum-subarray/maximum-subarrayV2.cpp b/maximum-subarray/maximum-subarrayV2.cpp
@@ -0,0 +1,54 @@
+#include <vector>
+#include <iostream>
+using namespace std;
+
+
+//Leet Ratings
+//       Speed  Memory
+//Total  121ms  67.8MB    
+//Beats  46.20% 63.61%
+//
+//Optimized to start iterating once a negative is reached in the prior
+//set of iterations.
+
+
+int maxSubArray(vector<int>& nums) {
+
+    int size = nums.size();
+    int i = 0;
+    long int current_val = 0;
+    long int highest = nums[0];
+    while(i < size){
+        current_val = nums[i];
+
+        //This is necessary in case the final value of a list is the highest value.
+        if(current_val > highest){
+            highest = current_val;
+        }
+        int x = i + 1;
+        while(x < size & current_val > 0){
+            current_val += nums[x];
+            if(current_val > highest){
+                highest = current_val;
+            }
+            x += 1;
+        }
+        if(x == size){
+            break;
+        }
+        if(current_val < 0){
+            i = x;
+        }
+        else{
+            i += 1;
+        }
+
+        current_val = 0;
+    }
+    return highest;
+} 
+
+int main(){
+        vector<int> vector = {10, -1, -10, 32, 3, -3};
+        cout << maxSubArray(vector) << endl;
+}