Skip to Content
Technical Articles
Author's profile photo Kallol Chakraborty

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
    INTERFACES if_oo_adt_classrun.

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

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

ENDCLASS.


CLASS zcl_algo_kadane IMPLEMENTATION.

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

  METHOD kadaneAlgorithm.

* 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

      7 Comments
      You must be Logged on to comment or reply to a post.
      Author's profile photo Hrishikesh Mangi
      Hrishikesh Mangi

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

      Author's profile photo Kallol Chakraborty
      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

      Author's profile photo Matt Dion
      Matt Dion

      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.
          INTERFACES if_oo_adt_classrun.
        PRIVATE SECTION.
      
          TYPES mty_t_num TYPE STANDARD TABLE OF i WITH DEFAULT KEY.
      
          METHODS kadane_algorithm
            IMPORTING it_nums       TYPE mty_t_num
            RETURNING VALUE(rv_max) TYPE i.
      
      ENDCLASS.
      
      CLASS zkadane_algorithm IMPLEMENTATION.
      
        METHOD if_oo_adt_classrun~main.
      
          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.
      
        METHOD kadane_algorithm.
      
          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.
      Author's profile photo Kallol Chakraborty
      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

      Author's profile photo Prasanth Padmanabhan Menon
      Prasanth Padmanabhan Menon

      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

      Author's profile photo Jacques Nomssi Nzali
      Jacques Nomssi Nzali

      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

      Author's profile photo Tao Wang
      Tao Wang

      Nice Blog. Thanks.