Solve the maximum subarray problem in Python

Introduction

Nice to meet you all. My name is ryuichi69.

Today, I will write the output of what I studied the algorithm here. Today we are dealing with an algorithm called maximum subarray problem . Please let us know in the comments if there are any parts that are difficult to understand or omissions in requirements.

What is the maximum subarray problem?

Well, this is the main subject. The maximum subsum problem is a problem that says, " There is an array containing integers in each element, and when you select some of them, find the maximum value of the total of those selected ".

Problem Let

n be an integer greater than or equal to 0. At this time, the sequence (array) a [k] consisting of n elements satisfies the following conditions.

  1. a [0], a [1], ..... a [n-1] is an integer
  2. It is assumed that each element of the sequence a is arranged in descending order. .. For all natural numbers i that satisfy 1 ≤ i ≤ (n-1), we satisfy a [i]> a [i + 1].

    Furthermore, let k be a natural number that satisfies 1 ≤ k ≤ n. Select any k elements from the sequence a [n]. Create a program in which the sum of the items selected at this time is S [k].

    Constraints
    1. 1≦n≦10
    2. 1≦k≦10
    3. -10≦a[k]≦10

    * Since this is an algorithm practice, we do not consider the amount of calculation.

    Input 1

    a = [7,9,-1,1,-4]
    k = 4
    * If a = [7,9, -1,1] and the elements of the array are not in descending order as described above, sort the elements of the array in descending order and total.

    Output 1

    17

    Input 2

    a = [-1,-2,-3,-4]
    k = 3
    * If all the elements are negative integers, they will not be added.

    Output 2

    0

    How to do (Kadane's algorithm) For each

    array, add in order from 0. And if the total value added is larger than before the addition, that value is adopted as S_k . Specifically,

    1. Sort the array in descending order
    2. Create a function max (a, b) that returns the larger of the integers a and b
    3. Increase k by 1. Go and consider the case where a [k] is added to the maximum sum value s [k-1] and the case where it is not added, and note (store) the larger value as s [k] in the array. (Dynamic planning method). Expressed in the formula,