Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
kadane2.cpp File Reference

Implementation of Kadane Algorithm More...

#include <array>
#include <climits>
#include <iostream>
Include dependency graph for kadane2.cpp:

Namespaces

namespace  dynamic_programming
 Dynamic Programming algorithms.
 
namespace  kadane
 Functions for Kadane algorithm.
 

Functions

template<size_t N>
int dynamic_programming::kadane::maxSubArray (const std::array< int, N > &n)
 maxSubArray function is used to calculate the maximum sum subarray and returns the value of maximum sum which is stored in the variable max_sum
 
int main ()
 Main function.
 

Detailed Description

Implementation of Kadane Algorithm

Kadane algorithm is used to find the maximum sum subarray in an array and maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum

Algorithm

The simple idea of the algorithm is to search for all positive contiguous segments of the array and keep track of maximum sum contiguous segment among all positive segments(curr_sum is used for this) Each time we get a positive sum we compare it with max_sum and update max_sum if it is greater than curr_sum

Author
Ayush Singh

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
60 {
61 const int N = 5;
62 std::array<int, N> n{}; // declaring array
63 // taking values of elements from user
64 for (int i = 0; i < n.size(); i++) {
65 std::cout << "Enter value of n[" << i << "]"
66 << "\n";
67 std::cin >> n[i];
68 }
69 int max_sum = dynamic_programming::kadane::maxSubArray<N>(
70 n); // calling maxSubArray function
71 std::cout << "Maximum subarray sum is " << max_sum; // Printing the answer
72
73 return 0;
74}
constexpr uint32_t N
A struct to represent sparse table for min() as their invariant function, for the given array A....
Definition sparse_table.cpp:47

◆ maxSubArray()

template<size_t N>
int dynamic_programming::kadane::maxSubArray ( const std::array< int, N > & n)

maxSubArray function is used to calculate the maximum sum subarray and returns the value of maximum sum which is stored in the variable max_sum

Template Parameters
Nnumber of array size
Parameters
narray where numbers are saved
Returns
the value of maximum subarray sum
42 {
43 int curr_sum =
44 0; // declaring a variable named as curr_sum and initialized it to 0
45 int max_sum = INT_MIN; // Initialized max_sum to INT_MIN
46 for (int i : n) { // for loop to iterate over the elements of the array
47 curr_sum += n[i];
48 max_sum = std::max(max_sum, curr_sum); // getting the maximum value
49 curr_sum = std::max(curr_sum, 0); // updating the value of curr_sum
50 }
51 return max_sum; // returning the value of max_sum
52}
T max(T... args)
Here is the call graph for this function: