[Java/Python] Stack keeps index of elements less than nums[i] - O(N)
Idea\n- ans = 0\n- For each element nums[i] in array nums:\n\t- We treat nums[i] as minimum number in subarray which includes nums[i]\n\t- ans = max(ans, nums[i
**Idea**\n- `ans = 0`\n- For each element `nums[i]` in array `nums`:\n\t- We treat `nums[i]` as minimum number in subarray which includes `nums[i]`\n\t- `ans = max(ans, nums[i] * getSum(left_bound_index, right_bound_index))`\n\t- `left_bound_index`: index of the farthest element greater or equal to `nums[i]` in the left side\n\t- `right_bound_index`: index of the farthest element greater or equal to `nums[i]` in the right side\n- How to build `left_bound/right_bound` array which store index of the farthest element greater or equal to `nums[i]` in the left side or in the right side?\n\t- Use stack `st` which keeps index of elements less than `nums[i]` so far\n\t- For `i` in `[0..n-1]`:\n\t\t- Pop all elements from `st` which are greater or equal to `nums[i]`\n\t\t- If `st` is not empty: `left_bound[i]` = `st[-1] + 1` (because `st[-1]` is index of the nearest element smaller than `nums[i]`)\n\t\t- else: `left_bound[i]` = `0` (because there is no element smaller than `nums[i]` so far)\n\t\t- Add `i` to `st`\n\n<iframe src="https://leetcode.com/playground/L87Hqcpk/shared" frameBorder="0" width="100%" height="650"></iframe>\n\n**Complexity**\n- Time: `O(N)`\n- Space: `O(N)`
[]