Technical Articles
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! 🙂
Can you please explain the practical use of this algorithm in SAP ERP scenario?
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:
Dear Matt Dion,
Thanks for checking out the blogpost. I have made the changes. Nice alternate solution.🙂
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
Best Regards,
Prasanth
I found this Scheme solution for the Greatest subsequential sum in the Rosetta Code repository:
It returns a 'cons' of the maximum sum and (one of) the maximum subsequences.
I confirmed it works with abap Scheme :
best regards,
Jacques Nomssi Nzali
Nice Blog. Thanks.