TheAlgorithms
Implement Maximum Sum of Non-Adjacent Elements
This PR adds an algorithm to find the maximum sum of non-adjacent elements in an array. The implementation includes two approaches:
Dynamic Programming with O(n) Space Complexity:
- Utilizes a dynamic programming array to store the maximum sum at each index.
- Time Complexity: O(n)
- Space Complexity: O(n)
Optimized Space Complexity Approach:
- Uses two variables to track the maximum sums, reducing space complexity to O(1).
- Time Complexity: O(n)
- Space Complexity: O(1)
- [x] I have read CONTRIBUTING.md.
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with
clang-format -i --style=file path/to/your/file.java
Related Issues : Issue #5510
Codecov Report
All modified and coverable lines are covered by tests :white_check_mark:
Project coverage is 60.21%. Comparing base (
c152c38) to head (eeb2936).
Additional details and impacted files
@@ Coverage Diff @@
## master #5544 +/- ##
============================================
+ Coverage 60.15% 60.21% +0.05%
- Complexity 3868 3876 +8
============================================
Files 562 563 +1
Lines 16009 16035 +26
Branches 3069 3073 +4
============================================
+ Hits 9631 9655 +24
- Misses 5973 5974 +1
- Partials 405 406 +1
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
Hi @siriak , I've addressed your feedback by fixing the Clang PR check and adding JUnit tests for the MaximumSumOfNonAdjacentElements class.