kadanes3.cpp File Reference

Efficient implementation for maximum contiguous subarray sum by Kadane's algorithm. More...

#include <array>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iostream>

Include dependency graph for kadanes3.cpp:

Go to the source code of this file.

Functions
template<std::size_t SIZE>
int	max_subarray_sum (std::array< int64_t, SIZE > arr, uint64_t length)
	for IO operations
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Efficient implementation for maximum contiguous subarray sum by Kadane's algorithm.

Our task is to take length of array and then the whole array as input from the user and then calculate the maximum contiguos subarray sum for the input array, using the kadane's algorithm.

There can be a case that all the elements in the input array are negative. In that case, the least value among all elements is the maximum sum with subarray length = 1.

Author

Abhijeet Tiwari

Definition in file kadanes3.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 60 of file kadanes3.cpp.

           {
    // Below is the code for accepting array from the user and then
    // calling the function for the required output.
    // It has been commented for now so that the test() function can run
    // and the test cases can be verified.
    // code for accepting array from user starts
 
    // std::size_t n;  // variable for length of input array
    // std::cout << "Enter length of the array: ";
    // std::cin >> n;
    // std::array<int64_t, 100> arr = {0};
    // // we need to give a constant in size. Hence we have allocated 100
    // for now.
    // for (int i = 0; i < n; i++)
    // taking input of each element of the array
    // {
    //     std::cin >> arr[i];
    // }
    // code for accepting array from user ends
 
    // int max_sum = max_subarray_sum(arr, n);
    // std::cout << "Maximum contiguous sum for this array is : " << max_sum
    //           << std::endl;
 
    test();  // run self-test implementations
    return 0;
}

max_subarray_sum()

template<std::size_t SIZE>

int max_subarray_sum	(	std::array< int64_t, SIZE >	arr,
		uint64_t	length )

for IO operations

for std::array for assert for INT_MIN value

Utility function to check the current maximum number

Parameters

arr	input array
length	length of the input array

Returns

maximum contiguous subarray sum

Definition at line 29 of file kadanes3.cpp.

                                                                   {
    int64_t current_max = INT_MIN, current_sum = 0;
    for (int i = 0; i < length; i++) {
        current_sum = current_sum + arr[i];
        if (current_max < current_sum) {
            current_max = current_sum;
        }
 
        if (current_sum < 0) {
            current_sum = 0;
        }
    }
    return current_max;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 48 of file kadanes3.cpp.

                   {
    std::array<int64_t, 4> arr = {1, 2, 3, 4};
    std::array<int64_t, 5> arr1 = {-1, -2, -4, -6, 7};
    assert(max_subarray_sum(arr, 4) == 10);
    assert(max_subarray_sum(arr1, 5) == 7);
    std::cout << "All test cases have passed!\n";
}