# Easy way to perform Kadane’s algorithm(Maximum Subarray) in SAP BTP ABAP(Steampunk), JS & Python

## Introduction

This is part of the Easy way to write algorithms in ABAP: Series 01. For more algorithms, please check the main blog-post.

## Problem

Given an integer array `nums`, find the subarray which has the `largest sum and return its sum`.

Example 1:

```Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

Example 2:

```Input: nums = [1]
Output: 1
```

Example 3:

```Input: nums = [5,4,-1,7,8]
Output: 23

```

Constraints:

• `1 <= nums.length <= 105`
• `-104 <= nums[i] <= 104`

## Solution

Time Complexity: O(n)

Space Complexity: O(1)

### ABAP

``````CLASS zcl_algo_kadane DEFINITION
PUBLIC
FINAL
CREATE PUBLIC .

PUBLIC SECTION.
* Mandatory declaration

PROTECTED SECTION.
PRIVATE SECTION.
TYPES ty_nums TYPE STANDARD TABLE OF i WITH EMPTY KEY.

IMPORTING lt_nums       TYPE STANDARD TABLE
RETURNING VALUE(rv_msf) TYPE i.

ENDCLASS.

out->write( |{ kadaneAlgorithm( VALUE ty_nums( ( 5 ) ( 4 ) ( -1 ) ( 7 ) ( 8 ) ) ) }| ).
ENDMETHOD.

* local variables
DATA : lv_meh   TYPE i VALUE 0, "max ending here
lv_temp  TYPE i VALUE 0, "sum
lv_start TYPE i VALUE 0, "start
lv_end   TYPE i VALUE 0. "end

rv_msf = VALUE #( lt_nums[ 1 ] OPTIONAL ).

LOOP AT lt_nums ASSIGNING FIELD-SYMBOL(<lf_wa>).

lv_meh += <lf_wa>.

IF ( rv_msf < lv_meh ).
rv_msf = lv_meh.
lv_start = lv_temp.
lv_end = ( sy-tabix -  1 ).
ENDIF.

IF ( lv_meh < 0 ).
lv_meh = 0.
lv_temp = sy-tabix.
ENDIF.
ENDLOOP.

UNASSIGN <lf_wa>.
FREE : lv_meh, lv_temp, lv_start, lv_end.

ENDMETHOD.

ENDCLASS.``````

### JavaScript

``````/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
/** lv_msf should start at -Infinity (or at the value of the first item of the array),
* otherwise an array containing all negative numbers won't give a proper result */
var lv_msf = -Infinity,
lv_meh = 0,
lv_start = 0,
lv_end = 0,
lv_temp = 0;

for (let i = 0; i < nums.length; i++) {
lv_meh += nums[i];

if (lv_msf < lv_meh) {
lv_msf = lv_meh;
lv_start = lv_temp;
lv_end = i;
}

if (lv_meh < 0) {
lv_meh = 0;
lv_temp = i + 1;
}
}

return lv_msf;

};``````

### Python

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:

# local variables
lv_msf = nums[0]
lv_meh = 0
lv_start = 0
lv_end = 0
lv_temp = 0

# running the loop
for i in range(0, len(nums)):
lv_meh += nums[i]

if (lv_msf < lv_meh):
lv_msf = lv_meh
lv_start = lv_temp
lv_end = i

if(lv_meh < 0):
lv_meh = 0
lv_temp = i + 1

return lv_msf``````

N.B: For ABAP, I am using SAP BTP ABAP Environment 2211 Release.

Happy Coding! 🙂

### Assigned Tags

You must be Logged on to comment or reply to a post.

Can you please explain the practical use of this algorithm in SAP ERP scenario?

Kallol Chakraborty
Blog Post Author

Dear Hrishikesh Mangi

Thanks for checking out the blogpost.

This algorithm can help you to find the max continuous working hours of an employee for a particular time period.

The purpose of writing this blog-post is purely for educational purposes. It is for developing the mindset for solving problems through ABAP. 🙂

Regards,

Kallol

FWIW: The comments in the JS version should be heeded. The ABAP version would give the wrong result given only negative values.

Here's an alternate that allows you to execute as many iterations of the algorithm that you want, plus includes negative value support:

``````CLASS zkadane_algorithm DEFINITION
PUBLIC
FINAL
CREATE PUBLIC .

PUBLIC SECTION.
PRIVATE SECTION.

TYPES mty_t_num TYPE STANDARD TABLE OF i WITH DEFAULT KEY.

IMPORTING it_nums       TYPE mty_t_num
RETURNING VALUE(rv_max) TYPE i.

ENDCLASS.

out->write( |{ kadane_algorithm( VALUE #( ( -2 ) ( 1 ) ( -3 ) ( 4 ) ( -1 ) ( 2 ) ( 1 ) ( -5 ) ( 4 ) ) ) }| ).
out->write( |{ kadane_algorithm( VALUE #( ( 1 ) ) ) }| ).
out->write( |{ kadane_algorithm( VALUE #( ( 5 ) ( 4 ) ( -1 ) ( 7 ) ( 8 ) ) ) }| ).
out->write( |{ kadane_algorithm( VALUE #( ( -5 ) ( -2 ) ( -8 ) ) ) }| ).

ENDMETHOD.

DATA: lv_meh TYPE i.

" calculate
LOOP AT it_nums ASSIGNING FIELD-SYMBOL(<lv_num>).
lv_meh += <lv_num>.
rv_max = COND #( WHEN sy-tabix = 1 OR rv_max < lv_meh THEN lv_meh ELSE rv_max ).
lv_meh = COND #( WHEN lv_meh < 0 THEN 0 ELSE lv_meh ).
ENDLOOP.

ENDMETHOD.

ENDCLASS.``````
Kallol Chakraborty
Blog Post Author

Dear Matt Dion,

Thanks for checking out the blogpost. I have made the changes. Nice alternate solution.🙂

``lv_msf = VALUE #( lt_nums[ 1 ] OPTIONAL ).``

Now, it should work fine.

Regards,

Kallol

Hi Kallol,

Great initiative 🙂

You can also use the syntax nmax to find the max value.

So in the end, you can make it as

``````DATA: lt_input TYPE STANDARD TABLE OF i WITH EMPTY KEY.

lt_input = VALUE #( ( -11 ) ( -1 ) ( -2 ) ( -7 ) ( -5 ) ( -23 ) ).

DATA(lv_maxval) = lt_input[ 1 ].
DATA(lv_curval) = lt_input[ 1 ].

LOOP AT lt_input ASSIGNING FIELD-SYMBOL(<fs_input>) FROM 2.
lv_curval = nmax( val1 = <fs_input> val2 = <fs_input> + lv_curval ).
lv_maxval = nmax( val1 = lv_curval val2 = lv_maxval ).
ENDLOOP.

out->write( lv_maxval ).``````

Best Regards,

Prasanth

I found this Scheme solution for the Greatest subsequential sum in the Rosetta Code repository:

``````(define (maxsubseq in)
(let loop
((_sum 0) (_seq (list)) (maxsum 0) (maxseq (list)) (l in))
(if (null? l)
(cons maxsum (reverse maxseq))
(let* ((x (car l)) (sum (+ _sum x)) (seq (cons x _seq)))
(if (> sum 0)
(if (> sum maxsum)
(loop sum seq    sum    seq (cdr l))
(loop sum seq maxsum maxseq (cdr l)))
(loop 0 (list) maxsum maxseq (cdr l)))))))``````

It returns a 'cons' of the maximum sum and (one of) the maximum subsequences.

I confirmed it works with abap Scheme :

``````(maxsubseq '(-2 1 -3 4 -1 2 1 -5 4))
=> (6 4 -1 2 1)
(maxsubseq '(1))
=> (1 1)
(maxsubseq '(5 4 -1 7 8))
=> (23 5 4 -1 7 8)``````

best regards,

Jacques Nomssi Nzali

Nice Blog. Thanks.