From 82ba233d73f0b5feb9bd046e1fc20a2f10dc34a9 Mon Sep 17 00:00:00 2001 From: crupest Date: Wed, 30 Sep 2020 15:16:06 +0800 Subject: import(solutions): Add problem 213 . --- works/solutions/cpp/213.cpp | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) create mode 100644 works/solutions/cpp/213.cpp (limited to 'works/solutions/cpp') diff --git a/works/solutions/cpp/213.cpp b/works/solutions/cpp/213.cpp new file mode 100644 index 0000000..1414222 --- /dev/null +++ b/works/solutions/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