Stack with Function min() - Interview Question&Answer
Question: A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n). For example, in the array { 1, -2, 3, 10, -4, 7, 2, -5 }, its sub-array { 3, 10, -4, 7, 2 } has the maximum sum 18. Analysis: During interviews, many candidates can solve it by enumerating all of sub-arrays and calculate their sum. An array with n elements has n(n+1)/2 sub-arrays. It costs O(n 2 ) time at least to calculate their sum. Usually the intuitive and forceful solution is not the most optimized one. Interviewers will tell us that there are better solutions. Solution 1: Analyze arrays number by number We try to accumulate every number in the example array from first to end. We initialize sum as 0. At our first step, add the first number 1, and sum is 1. And then if we add the second number -2, sum becomes -1. ...
