Merge pull request kennyledet#515 from mike168m/master

Kendrick Ledet · web-flow · commit 900d4e2b660b · 2017-07-28T15:25:12.000-07:00
Add maximum sub array sum in C++
diff --git a/Depth_First_Search/C++/mike168m/Depth_First_Search.h b/Depth_First_Search/C++/mike168m/Depth_First_Search.h
@@ -0,0 +1,80 @@
+#pragma once
+
+#include <iostream>
+#include <vector>
+#include <iterator>
+#include <algorithm> // hehe... algoception :)
+#include <list>
+
+// an undirected graph
+template<class Type>
+class Graph
+{
+public:
+    int vertices;
+    int edges;
+    std::vector<std::vector<Type>> adjList;
+
+    explicit Graph(int numVertices)
+        :vertices(numVertices), edges(0)
+    {
+        adjList = std::vector<std::vector<Type>>(vertices);
+        std::generate(adjList.begin(), adjList.end(), []{
+           return std::vector<Type>{};
+        });
+    }
+
+    ~Graph() = default;
+
+    void add(Type v, Type w) {
+        adjList[v].push_back(w);
+        adjList[w].push_back(v);
+        edges++;
+    }
+
+    std::vector<Type>& adj(Type v) {
+        return adjList[v];
+    }
+
+    std::string to_string() const {
+        std::string str;
+        for (int i = 0; i < vertices; i++) {
+            str += std::to_string(i) + "\n";
+            for (auto t : adj(i)) {
+                str += "\t" + t;
+            }
+        }
+
+        return str;
+    }
+};
+
+template<class Type>
+class DepthFirstSearch {
+    const Type startVertex;
+    Graph<Type>& graph;
+    std::vector<bool> markedVertexes;
+public:
+    DepthFirstSearch(Graph<Type>& _graph, Type _startVertex)
+        :startVertex(_startVertex), graph(_graph)
+    {
+        markedVertexes = std::vector<bool>(_graph.vertices);
+    }
+
+    void dfs() {
+        dfs_impl(graph, this->startVertex);
+    }
+
+    void dfs_impl(Graph<Type>& _graph, Type start) {
+        markedVertexes[start] = true;
+        for (const Type& t : _graph.adj(start)) {
+            if (!markedVertexes[t]) {
+                dfs_impl(_graph, t);
+            }
+        }
+    }
+};
+
+
+
+
diff --git a/Depth_First_Search/C++/mike168m/Depth_First_Search_Test.cpp b/Depth_First_Search/C++/mike168m/Depth_First_Search_Test.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+#include <string>
+#include "graph.h"
+
+
+int main() {
+    int key = 0;
+    Graph<int> g(13);
+    g.add(0, 5);
+    g.add(0, 6);
+    g.add(1, 6);
+
+    DepthFirstSearch<int> depthFirstSearch(g, 6);
+    depthFirstSearch.dfs();
+
+    std::cin >> key;
+}
diff --git a/Linear_Search/x86_Asm/mike168m/linear_search.asm b/Linear_Search/x86_Asm/mike168m/linear_search.asm
@@ -0,0 +1,40 @@
+TITLE Linear/Sequential search implemented in x86 assembly (MASM)
+; Search for a value in an array of bytes by comparing each value with a key
+; return the position of the key
+; O(n) time complexity
+; the address of the first element in the array must be in the edx
+; and the arrays length in the ecx register
+; the index of the key is returned in the eax register
+
+.386	; minimum CPU required to run the program
+.model flat, stdcall ; identifies the memory model for the program,
+					; in this case its protected mode. It also tells which 
+					; calling convention to use for procedures
+.stack 4096
+
+.data
+data db 42, 40, 70, 90, 62, 70, 40 ; our array of data
+
+.code
+; implementation of sequential search
+SequentialSearch PROC
+	xor eax, eax 			; clear eax register just in case
+BEGIN_LOOP:					
+	cmp BYTE PTR[edx], bl   ; if [edx] == bl
+	je FOUND				;    then goto FOUND
+	inc eax                 ; else increment eax
+	inc edx                 ; increment edx
+	loop BEGIN_LOOP			; automatically decrements ecx register
+FOUND:
+	ret
+SequentialSearch ENDP
+
+; entry point
+main PROC
+	mov bl, 90 ; search for 92 in array
+	mov edx, OFFSET data
+	mov ecx, LENGTHOF data
+	call SequentialSearch
+main ENDP
+
+END main
diff --git a/Maximum_Subarray/C++/mike168m/max_sub_array.cpp b/Maximum_Subarray/C++/mike168m/max_sub_array.cpp
@@ -0,0 +1,31 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+template<typename T>
+T kadane_method(const std::vector<T>& v){
+	T ret = 0;
+	std::for_each(v.begin(), v.end(), [c_max = 0, max = 0, &ret](T m) mutable {
+		c_max  = c_max + m;
+		// the ccurrent max is a negative number,
+		// we can't use that cuz it will not give us
+		// the maximum sum
+		if (c_max < 0) c_max = 0;
+		// we have to check if there is a new max
+		// if c_max is greater than it means there is a new max so we 
+		// have to use that instead.
+		if (max < c_max) max = c_max;
+
+		//std::cout << "m: " << m << " c_max: " 
+		//			<< c_max << " max: " << max << '\n';
+		ret = max; 
+	});
+
+	return ret;
+}
+
+int main() {
+	std::cout << kadane_method<int>({-2, -3, 4, -1, -2, 1, 5, -3}) << '\n';
+	std::cout << kadane_method<int>({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << '\n';
+	std::cout << kadane_method<int>({2, 3, 7, -5, -1, 4, -10}) << '\n';
+}
