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! 🙂