Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Solution
Look at the problem, we can find the keyword -【contiguous 】, that means we will use iteration to solve the it.
C# Solution
❌First try – Time Limit Exceeded
public class Solution {
public int MaxSubArray(int[] nums) {
int max = (int)Math.Pow(10, 4)*-1 -1;
for(int i = 0;i<nums.Length;i++)
{
int tmp = nums[i];
if(tmp>max)
{
max = tmp;
}
for(int j = i+1;j<nums.Length;j++)
{
tmp+=nums[j];
if(tmp>max)
{
max = tmp;
}
}
}
return max;
}
}
In this first try, we used a easy nested loop to find out the max value, but the poor time complexity makes it 【Time Limit Exceeded】.
Time Complexity : O(n2)
Solution1 – iteration
In this solution, if the sum of elements is greater than 0, we will keep the sum to the next iteration, or we will reset it to 0.
public class Solution {
public int MaxSubArray(int[] nums) {
int max = nums[0];
int tmp =0;
for(int i = 0;i<nums.Length;i++)
{
tmp+=nums[i];
if(tmp>max)
{
max = tmp;
}
if(tmp<0)
{
tmp = 0;
}
}
return max;
}
}
Runtime : 270ms、206ms、249ms
Time Complexity : O(n)
Java Solution
Solution1
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int tmp =0;
for(int i = 0;i<nums.length;i++)
{
tmp+=nums[i];
if(tmp>max)
{
max = tmp;
}
if(tmp<0)
{
tmp = 0;
}
}
return max;
}
}
Runtime : 2ms、1ms、1ms ≈ Faster than 100% ( 1ms )
Time Complexity : O(n)
Python3 Solution
Solution1
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max = nums[0]
tmp =0
for i in range(0,len(nums)):
tmp+=nums[i]
if(tmp>max):
max = tmp
if(tmp<0):
tmp = 0
return max
Runtime : 692ms、674ms、897ms
Time Complexity : O(n)
JavaScript Solution
Solution1
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var max = nums[0];
var tmp =0;
for(var i = 0;i<nums.length;i++)
{
tmp+=nums[i];
if(tmp>max)
{
max = tmp;
}
if(tmp<0)
{
tmp = 0;
}
}
return max;
};
🧡You can support me by clicking some ad, Thanks a lot
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};