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