FunctionArrayMaxSubKadanesAlgorithm
// This source code is subject to the terms of the Mozilla Public License 2.0 at https://mozilla.org/MPL/2.0/
// © RicardoSantos

//@version=5

// @description Implements Kadane's maximum sum sub array algorithm.
library("FunctionArrayMaxSubKadanesAlgorithm")

// reference:
//      https://en.wikipedia.org/wiki/Maximum_subarray_problem
//      https://javabypatel.blogspot.com/2015/08/find-largest-sum-contiguous-subarray-using-Kadane-algorithm.html

import RicardoSantos/DebugConsole/3 as console
[__T, __C] = console.init(20)

// @function Kadanes algorithm.
// @param samples float array, sample data values.
// @returns float.
export size (float[] samples) => //{
	int _size_s = array.size(samples)
    //
    switch
        (_size_s < 1) => runtime.error('FunctionArrayMaxSubKadanesAlgorithm -> size(): "samples" has the wrong size.')
    //
    float _max_sum = array.get(samples, 0)
    float _current_sum = _max_sum
    for _i = 1 to _size_s-1
        float _si = array.get(samples, _i)
        _current_sum := math.max(_current_sum + _si, _si)
        _max_sum := math.max(_max_sum, _current_sum)
    _max_sum
//{ usage:
console.queue_one(__C, str.format('maximum sum sub array size:{0}', size(array.from(-2.0, 1, -3, 4, -1.5, 2, 1, -5, -2, 5))))
console.queue_one(__C, str.format('maximum sum sub array size:{0}', size(array.from(-2.0, 1, 3, -2, 1, 4, -5, 1))))
//}}

// @function Kadane's algorithm with indices.
// @param samples float array, sample data values.
// @returns tuple with format [float, int, int].
export indices (float[] samples) =>
	int _size_s = array.size(samples)
    //
    switch
        (_size_s < 1) => runtime.error('FunctionArrayMaxSubKadanesAlgorithm -> indices(): "samples" has the wrong size.')
    //
    float _max_sum = array.get(samples, 0)
    float _current_sum = _max_sum
    int _start = 0, int _end = 0, int _s = 0
    for _i = 1 to _size_s-1
        float _si = array.get(samples, _i)
        _current_sum := math.max(_current_sum + _si, _si)
        if _current_sum > _max_sum
            _max_sum := _current_sum
            _start := _s
            _end := _i
        if _current_sum < 0
            _current_sum := 0
            _s := _i + 1
    [_max_sum, _start, _end]
//{ usage:
[ki_0, kistart_0, kiend_0] = indices(array.from(-2.0, 1, -3, 4, -1, 2, 1, -5, -2, 5))
[ki_1, kistart_1, kiend_1] = indices(array.from(-2.0, 1, 3, -2, 1, 4, -5, 1))
console.queue_one(__C, str.format('maximum sum sub array size: {0} start:{1} end:{2}', ki_0, kistart_0, kiend_0))
console.queue_one(__C, str.format('maximum sum sub array size: {0} start:{1} end:{2}', ki_1, kistart_1, kiend_1))
//}}


console.update(__T, __C)