Notes

Integer.MAX_VALUE and Integer.MIN_VALUE usages

Be careful when using Integer.MAX_VALUE and Integer.MIN_VALUE with arithmetic operations (adding or substracting a value into them) together for holding the min and max values. It may cause overflow. For example; consider "53. Maximum Subarray" problem with given parameter nums = int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}:

1 public int maxSubArray(int[] nums) {
2        int preSum = Integer.MIN_VALUE;
3        int finalSum = Integer.MIN_VALUE;
4        for(int i = 0; i<nums.length; i++){
5            preSum = Math.max(preSum + nums[i], nums[i]);
6            finalSum = Math.max(finalSum, preSum);
7        }
8        return finalSum;
9 }

preSum is equal to Integer.MIN_VALUE (-2147483648). In line #5, we try to add -2 (nums[0]) to it. So the "preSum + nums[i]" become "-2147483648 + (-2)" and the result would become 2147483646. And that leads us to wrong result.

There's two different approaches to avoid this situation:

a) We can use the given constraints. In the example, one of the constraints given is "-10^5 <= nums[i] <= 10^5". So we can initialize preSum and finalSum accordingly:

2        int preSum = -100000; // -10^5
3        int finalSum = -100000; // -10^5

b) We can initialize preSum and finalSum with first (i=0) element of the array and start iterating over the array with second (i=1) element :

2        int preSum = nums[0];
3        int finalSum = nums[0];
4        for(int i = 1; i<nums.length; i++){
...      ...

Ref.: why Integer.MAX_VALUE + 1 == Integer.MIN_VALUE?

---