dynamic_programming/max_sub_array.py · 吴铭/Python -算法集

Fetch the repository succeeded.

richgiteeai

Watch

Unwatch Watching Releases Only Ignoring

1 Star 0 Fork 324

吴铭/Python -算法集

forked from 编程语言算法集/Python

Code Issues 0 Pull Requests 0 Wiki Insights Pipelines

Service

Tencent Cloud Serverless

Create your Gitee Account

Explore and code with more than 14 million developers,Free private repositories !:)

Already have an account? Sign in

文件

master

Branches (55)

Manage

master

add_issue_templates

mypy-reality-check

Python-3.10-beta-1

bubble_sort

Fix-validate_initial_digits-of-credit_card_validator.py

long-running-tests

fix-project-euler-problem-15

mypy-project-euler-092-sol-1

Add-tests-to-morse_code.py

from-__future__-import-annotations

flake8-bugbear

is_ip_v4_address_valid.py

cclauss-patch-4

cclauss-patch-3

mypy_--install-types_--non-interactive

Write-for-current-Python

harris_corner.py

dhruvmanila-patch-1

refactor/action

Clone or Download

Clone/Download

HTTPS SSH SVN SVN+SSH Download ZIP

Prompt

To download the code, please copy the following command and execute it in the terminal

To ensure that your submitted code identity is correctly recognized by Gitee, please execute the following command.

git config --global user.name userName 
git config --global user.email userEmail

When using the SSH protocol for the first time to clone or push code, follow the prompts below to complete the SSH configuration.

1 Generate RSA keys.

2 Obtain the content of the RSA public key and configure it in SSH Public Keys

To use SVN on Gitee, please visit the usage guide

When using the HTTPS protocol, the command line will prompt for account and password verification as follows. For security reasons, Gitee recommends configure and use personal access tokens instead of login passwords for cloning, pushing, and other operations.

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # Private Token

Branches 55

Tags 0

Python

dynamic_programming

max_sub_array.py

max_sub_array.py 2.58 KB

"""
author : Mayank Kumar Jha (mk9440)
"""
from __future__ import annotations

def find_max_sub_array(A, low, high):
 if low == high:
 return low, high, A[low]
 else:
 mid = (low + high) // 2
 left_low, left_high, left_sum = find_max_sub_array(A, low, mid)
 right_low, right_high, right_sum = find_max_sub_array(A, mid + 1, high)
 cross_left, cross_right, cross_sum = find_max_cross_sum(A, low, mid, high)
 if left_sum >= right_sum and left_sum >= cross_sum:
 return left_low, left_high, left_sum
 elif right_sum >= left_sum and right_sum >= cross_sum:
 return right_low, right_high, right_sum
 else:
 return cross_left, cross_right, cross_sum

def find_max_cross_sum(A, low, mid, high):
 left_sum, max_left = -999999999, -1
 right_sum, max_right = -999999999, -1
 summ = 0
 for i in range(mid, low - 1, -1):
 summ += A[i]
 if summ > left_sum:
 left_sum = summ
 max_left = i
 summ = 0
 for i in range(mid + 1, high + 1):
 summ += A[i]
 if summ > right_sum:
 right_sum = summ
 max_right = i
 return max_left, max_right, (left_sum + right_sum)

def max_sub_array(nums: list[int]) -> int:
 """
 Finds the contiguous subarray which has the largest sum and return its sum.

>>> max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])
 6

An empty (sub)array has sum 0.
 >>> max_sub_array([])
 0

If all elements are negative, the largest subarray would be the empty array,
 having the sum 0.
 >>> max_sub_array([-1, -2, -3])
 0
 >>> max_sub_array([5, -2, -3])
 5
 >>> max_sub_array([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
 187
 """
 best = 0
 current = 0
 for i in nums:
 current += i
 if current < 0:
 current = 0
 best = max(best, current)
 return best

if __name__ == "__main__":
 """
 A random simulation of this algorithm.
 """
 import time
 from random import randint

from matplotlib import pyplot as plt

inputs = [10, 100, 1000, 10000, 50000, 100000, 200000, 300000, 400000, 500000]
 tim = []
 for i in inputs:
 li = [randint(1, i) for j in range(i)]
 strt = time.time()
 (find_max_sub_array(li, 0, len(li) - 1))
 end = time.time()
 tim.append(end - strt)
 print("No of Inputs Time Taken")
 for i in range(len(inputs)):
 print(inputs[i], "\t\t", tim[i])
 plt.plot(inputs, tim)
 plt.xlabel("Number of Inputs")
 plt.ylabel("Time taken in seconds ")
 plt.show()

Copy Edit Raw Blame History

Christian Clauss authored 2020年09月23日 19:30 +08:00 . from future import annotations (#2464)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

"""
author : Mayank Kumar Jha (mk9440)
"""
from __future__ import annotations


def find_max_sub_array(A, low, high):
 if low == high:
 return low, high, A[low]
 else:
 mid = (low + high) // 2
 left_low, left_high, left_sum = find_max_sub_array(A, low, mid)
 right_low, right_high, right_sum = find_max_sub_array(A, mid + 1, high)
 cross_left, cross_right, cross_sum = find_max_cross_sum(A, low, mid, high)
 if left_sum >= right_sum and left_sum >= cross_sum:
 return left_low, left_high, left_sum
 elif right_sum >= left_sum and right_sum >= cross_sum:
 return right_low, right_high, right_sum
 else:
 return cross_left, cross_right, cross_sum


def find_max_cross_sum(A, low, mid, high):
 left_sum, max_left = -999999999, -1
 right_sum, max_right = -999999999, -1
 summ = 0
 for i in range(mid, low - 1, -1):
 summ += A[i]
 if summ > left_sum:
 left_sum = summ
 max_left = i
 summ = 0
 for i in range(mid + 1, high + 1):
 summ += A[i]
 if summ > right_sum:
 right_sum = summ
 max_right = i
 return max_left, max_right, (left_sum + right_sum)


def max_sub_array(nums: list[int]) -> int:
 """
 Finds the contiguous subarray which has the largest sum and return its sum.

 >>> max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])
 6

 An empty (sub)array has sum 0.
 >>> max_sub_array([])
 0

 If all elements are negative, the largest subarray would be the empty array,
 having the sum 0.
 >>> max_sub_array([-1, -2, -3])
 0
 >>> max_sub_array([5, -2, -3])
 5
 >>> max_sub_array([31, -41, 59, 26, -53, 58, 97, -93, -23, 84])
 187
 """
 best = 0
 current = 0
 for i in nums:
 current += i
 if current < 0:
 current = 0
 best = max(best, current)
 return best


if __name__ == "__main__":
 """
 A random simulation of this algorithm.
 """
 import time
 from random import randint

 from matplotlib import pyplot as plt

 inputs = [10, 100, 1000, 10000, 50000, 100000, 200000, 300000, 400000, 500000]
 tim = []
 for i in inputs:
 li = [randint(1, i) for j in range(i)]
 strt = time.time()
 (find_max_sub_array(li, 0, len(li) - 1))
 end = time.time()
 tim.append(end - strt)
 print("No of Inputs Time Taken")
 for i in range(len(inputs)):
 print(inputs[i], "\t\t", tim[i])
 plt.plot(inputs, tim)
 plt.xlabel("Number of Inputs")
 plt.ylabel("Time taken in seconds ")
 plt.show()