TheAlgorithms / C-Plus-Plus

Collection of various algorithms in mathematics, machine learning, computer science and physics implemented in C++ for educational purposes.
https://thealgorithms.github.io/C-Plus-Plus
MIT License
30.63k stars 7.26k forks source link

[FEATURE]Create Kadane's Algorithm #1038

Closed AlKun25 closed 4 years ago

AlKun25 commented 4 years ago

It is a very commonly used algorithm for sub-array problems.

Detailed Description

It is most famously used in the "maximum sum of sub array" question. The reason being that Kadane's algorithm has a time complexity of O(n), in comparison to the O(n^2) using traditional methods.

Context

Sub-array problems are very common kind of questions, also asked in many Coding Interviews. There have been multiple pull requests made to include Kadane's algorithm in the repository. This only supplements the importance of adding this algorithm to the repository. Also this is one of the unknown type of algorithm, which can help a lot.

Possible Implementation

Multiple pull requests are available by the name "Kadane" in the very same repository

I hope this issue will be attended and dealt with.

kvedala commented 4 years ago

Thank you.

  1. Feel free to create a pull-request to submit your contribution
  2. you mention of multiple pull-requests available - are they for this repo? We are not affiliated with other repos outside of the organization and do not copy code from others, unless the author shares the code following the repo licensing agreement as provided for in the pull-request template.
AlKun25 commented 4 years ago

Thank you.

  1. Feel free to create a pull-request to submit your contribution
  2. you mention of multiple pull-requests available - are they for this repo? We are not affiliated with other repos outside of the organization and do not copy code from others, unless the author shares the code following the repo licensing agreement as provided for in the pull-request template.

I meant that there are multiple pull-requests of the algorithm present in this repository itself. In case there is something missing in their pull-requests, let me know. Then, I will make a pull-request myself.

kvedala commented 4 years ago

Thank you.

  1. Feel free to create a pull-request to submit your contribution
  2. you mention of multiple pull-requests available - are they for this repo? We are not affiliated with other repos outside of the organization and do not copy code from others, unless the author shares the code following the repo licensing agreement as provided for in the pull-request template.

I meant that there are multiple pull-requests of the algorithm present in this repository itself. In case there is something missing in their pull-requests, let me know. Then, I will make a pull-request myself.

Got it. Could you mark the PR or comment in the one you are referring to so that it comes to our notice. I see the following

Thanks.

ayush523 commented 4 years ago

Hi, I would like to work on this issue. Should I create a new Kadane.cpp file and merge?