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.
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].
* Since this is an algorithm practice, we do not consider the amount of calculation.
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.
17
a = [-1,-2,-3,-4]
k = 3
* If all the elements are negative integers, they will not be added.
0
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,
Recommended Posts
Python program
solve.php
# a[i]To arrange each element of
#Bubble sort the array once
def bsort(arr):
#For replacement
temp = 0
#Double loop{Computational complexity is O(n^2)}
for i in range(0,len(arr)-1):
for j in range(0,len(arr)-1):
#This time it is in descending order, so the next element is from the current element
#Only if it is large, it will be replaced.
if(arr[j] < arr[j+1]):
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
#Two integers a,Returns the larger of b
def max(a,b):
if a > b:
return a
return b
def solve(arr,k):
#First sort the array in descending order
b = bsort(arr)
#Dynamic programming(dp)Make a note of the total value of each stage
dp = [0] * len(arr)
#Calculate dp{Computational complexity is O(n)}
for i in range(0,len(b)):
# dp[0](initialvalue)To decide
if i == 0:
#B if the elements of the array are integers greater than 0[0]
#Dp 0 if the elements of the array are integers less than 0[0]Adopt to
#Since it is sorted in descending order by bubble sort, b[0] <If 0
#After that, all sum dp[i]Will be 0
dp[0] = max(b[0],0)
else:
# dp[i-1]+b[i]>dp[i-1]Only in the case of dp[i]Adopted for
#Otherwise dp[i-1]Dp[i]Adopted for
#I'm sorry. Corrected(2019.12.29)
dp[i] = max(dp[i-1]+b[i],dp[i-1])
#Dp corresponding to the second argument[k]return it
return dp[k-1]
#for test
if __name__ == "__main__":
a = [7,9,-1,1,-4]
print(solve(a,4))
b = [-1,-2,-3,-4]
print(solve(b,3))
Reference
Ark's Blog | Kadane’s Algorithm |Maximum subarray problem
Qiita | Algorithm and data structure in C # 1 ~ Maximum partial array problem ~