From 185ef9fcb0e59f13e9ee0ccb261693cdaddebab0 Mon Sep 17 00:00:00 2001 From: crupest Date: Tue, 23 Feb 2021 21:07:19 +0800 Subject: import(solutions): Move leetcode solutions to subdir. --- works/solutions/leetcode/cpp/213.cpp | 41 ++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 works/solutions/leetcode/cpp/213.cpp (limited to 'works/solutions/leetcode/cpp/213.cpp') diff --git a/works/solutions/leetcode/cpp/213.cpp b/works/solutions/leetcode/cpp/213.cpp new file mode 100644 index 0000000..cd98f67 --- /dev/null +++ b/works/solutions/leetcode/cpp/213.cpp @@ -0,0 +1,41 @@ +#include + +using std::vector; + +class Solution +{ +public: + int rob(vector &nums) + { + int count = nums.size(); + if (count == 0) + return 0; + + if (count == 1) + return nums.front(); + + int not_rob_prev = 0; + int rob_prev = nums.front(); + int not_rob_prev_and_not_rob_first = 0; + int rob_prev_and_not_rob_first = 0; + + for (int i = 1; i < count - 1; i++) + { + int not_rob_prev_cache = not_rob_prev; + int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first; + not_rob_prev = std::max(not_rob_prev_cache, rob_prev); + rob_prev = std::max(not_rob_prev_cache + nums[i], not_rob_prev); + not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first); + rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[i], not_rob_prev_and_not_rob_first); + } + + // last houst + { + int not_rob_prev_and_not_rob_first_cache = not_rob_prev_and_not_rob_first; + not_rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache, rob_prev_and_not_rob_first); + rob_prev_and_not_rob_first = std::max(not_rob_prev_and_not_rob_first_cache + nums[count - 1], not_rob_prev_and_not_rob_first); + } + + return std::max(rob_prev, rob_prev_and_not_rob_first); + } +}; -- cgit v1.2.3