How to write the maxint without using the library?

Question

I am not sure what maxint is, and what it does. But I am trying to solve this problem without using maxint, possibly write another function to do this.

I would like to write this function without using:

from sys import maxint

Here is what I am trying to implement without using maxint.

def maxSubArraySum(a,size):

    maxi = -maxint - 1
    maxi_ends = 0

    for i in range(0, size):
        maxi_ends = maxi_ends + a[i]
        if (maxi < maxi_ends):
            maxi = maxi_ends

        if maxi_ends < 0:
            maxi_ends = 0
    return maxi

This is someone not understanding how `int` objects work in Python. `maxint` is not appropriate here, since I can easily create smaller/ bigger integers. An appropriate value would be something like `maxi = float('-inf')`. — juanpa.arrivillaga, Jan 21 '20 at 17:32
`sys.maxint` was [removed in Python 3](https://docs.python.org/3/whatsnew/3.0.html#integers). You might be able to use `sys.maxsize` instead — although it's unclear whether you understand the meaning of either of these constants. — martineau, Jan 21 '20 at 17:48
This code is unclear. Why do you create the variable `max_ending_here` and then never use it? What is the purpose of the `maxi_ends` variable, when it is guaranteed to always be zero? — John Gordon, Jan 21 '20 at 17:52
There's no limit to the size of integers in Python (other than how much memory is available), so `maxint` is meaningless. This may be an [XY Problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). What are you trying to calculate in your function? — martineau, Jan 21 '20 at 17:56

score 0 · Answer 1 · answered Jan 22 '20 at 03:08

this is a common pattern in programming (see this answer): to find the maximum number in a list, initialize ans to a value that's guaranteed to be lower than anything else in the list, then go through the list and simply perform the operation

if element > ans:
    ans = element

alternatively, you could set ans to be the value of the first value, but this is less elegant, since you need to check for the existence of the first element (otherwise, if the list is empty, you will get an error). Or, the "list" might not be an actual list, but rather an iterator, like in your example, so getting the first value would be messy.

Anyways, that's the point of initializing your variable to be an extreme value. MaxInt, in other languages like java and C, are very useful and nice to use as this extreme value, because the values you encounter along the way are literally not possibly bigger than MaxInt.

But note that, as I said in the very beginning, the point of infinity/maxint/minint is only to be larger/smaller than anything you could possibly encounter. So, for problems like the one you posted, you can usually easily make yourself a lower-bound for the smallest possible value of any maxi_ends. And you can make it a really loose lower-bound too (it doesn't have to be realistically attainable). So here, one way to find the lowest possible value of maxi_ends would be the sum of all the negative values in a. maxi_ends can't possibly go any lower than that.

Even easier, if you know what the smallest possible value of a[i] is, and you know the maximum possible length of a, you can calculate the smallest possible value that maxi_end could take for any input, right off the bat. This is useful in these kinds of abstract programming problems that you see on coding competitions, coding interview prep, and homework, especially since you just need a quick and dirty solution. For example, if a[i] can't be any less than -100, and len(a) is at most 1000, then maxi_end will never exceed -100 * 1000 = -100000, so you can just write maxi = -100001.

It's also a useful python trick in some real life situations (again, where you only need a quick hack) to pick a preposterously large number if you are lazy -- for example, if you're estimating the shortest path, in miles, between two buildings in a road network -- you could just pick 1000000000000 as an upper-bound, since you know no path will ever be that high.

I don't know why you don't want to use sys.maxint (although as the comments say, it's a good idea not to use it), but there are actual ways to represent infinity in python: in python 3.5 or above, you can do

import math
test = math.inf

and otherwise, you can use float('inf').

How to write the maxint without using the library?

1 Answers1