Skip to content

Instantly share code, notes, and snippets.

@jrjames83

jrjames83/max_subarray_python.ipynb

Created January 30, 2018 03:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jrjames83/c23be13b273c32b74861e09d97dd1d1b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jrjames83/c23be13b273c32b74861e09d97dd1d1b to your computer and use it in GitHub Desktop.
Download ZIP
Python Maximium Subarray - Greedy Solution With Algorithmic Complexity via %time
Display the source blob
Display the rendered blob
Raw
max_subarray_python.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"data = [1,2,3,-9,5,7,-99,2,8] # Should be 12\n",
"# What are the indices "
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def max_subarr_brute(input_array):\n",
" global_max = 0\n",
" indices = []\n",
" for x in range(len(input_array)+1):\n",
" for j in range(len(input_array)+1):\n",
" if data[x:j]:\n",
" current_max = sum(input_array[x:j])\n",
" # print(current_max, data[x:j])\n",
" if current_max > global_max:\n",
" global_max = current_max\n",
" indices.append((x, j-1))\n",
" return global_max, indices.pop()"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(12, (4, 5))"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max_subarr_brute(data)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# O n ^2 n log n, n"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 519 µs, sys: 508 µs, total: 1.03 ms\n",
"Wall time: 584 µs\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/jeff/anaconda/envs/3point6/lib/python3.6/site-packages/ipykernel/__main__.py:1: DeprecationWarning: This function is deprecated. Please call randint(-200, 300 + 1) instead\n",
" if __name__ == '__main__':\n"
]
},
{
"data": {
"text/plain": [
"(396, (6, 9))"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy as np\n",
"\n",
"%time max_subarr_brute(np.random.random_integers(-200, 300, size=10))"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 6.57 ms, sys: 690 µs, total: 7.26 ms\n",
"Wall time: 6.7 ms\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/jeff/anaconda/envs/3point6/lib/python3.6/site-packages/ipykernel/__main__.py:1: DeprecationWarning: This function is deprecated. Please call randint(-200, 300 + 1) instead\n",
" if __name__ == '__main__':\n"
]
},
{
"data": {
"text/plain": [
"(6435, (0, 90))"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time max_subarr_brute(np.random.random_integers(-200, 300, size=100))"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/jeff/anaconda/envs/3point6/lib/python3.6/site-packages/ipykernel/__main__.py:1: DeprecationWarning: This function is deprecated. Please call randint(-200, 300 + 1) instead\n",
" if __name__ == '__main__':\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 511 ms, sys: 8.3 ms, total: 520 ms\n",
"Wall time: 566 ms\n"
]
},
{
"data": {
"text/plain": [
"(46106, (2, 999))"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time max_subarr_brute(np.random.random_integers(-200, 300, size=1000))"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/jeff/anaconda/envs/3point6/lib/python3.6/site-packages/ipykernel/__main__.py:1: DeprecationWarning: This function is deprecated. Please call randint(-200, 300 + 1) instead\n",
" if __name__ == '__main__':\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 48.2 s, sys: 223 ms, total: 48.4 s\n",
"Wall time: 48.8 s\n"
]
},
{
"data": {
"text/plain": [
"(508677, (0, 9997))"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%time max_subarr_brute(np.random.random_integers(-200, 300, size=10000))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python [conda env:3point6]",
"language": "python",
"name": "conda-env-3point6-py"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.1"
}
},
"nbformat": 4,
"nbformat_minor": 1
}
@Gatkuoth
Copy link

Gatkuoth commented Sep 21, 2018

thanks you so much you have helped me a lot

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment