The challenge of finding a contiguous subarray with the biggest sum using a given one-dimensional array is known as the subarray problem. For example, the contiguous subarray with the biggest sum in the array [-2, -3, 4, -1, -2, 1, 5, -3] is [4, 1, -2, 1, 5] and the sum is 7. The problem has the following cases:
- If the array includes only non-negative values, the problem is solved. the largest subarray will be the entire array.
- If the array includes only non-positive values, a solution is any subarray of size 1 holding the array's maximum value. We will solve this problem using python with different algorithms like brute force, Divide and conquer and dynamic programming then compares their results.
The algorithm will be analyzed using two methods (Analytical – Empirical). In the Empirical Method we will rely on two testing method:
- timeit Library: to calculate the execution time from the start of function call to the end of it.
- Leetcode: problem solving platform provide test cases and analysis to your algorithm.
For more details and results:
documentation : https://bit.ly/3uQvZJ1
colab live : https://colab.research.google.com/drive/1VaTmQw_9LYHatCtj-guSV4-QHu66q11n?usp=sharing
Ali Mohamed - aly.cfr16@gmail.com