Topic tags :- Array, Divide and Conquer, Dynamic Programming
Question type :- Easy
Question link : Maximum Subarray
Note : Try yourself before seeing solution here.
Question :
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.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Constraints:
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
Follow up: If you have figured out the O(n) solution, try coding another
solution using the divide and conquer approach, which is more subtle.
Solutions : in Java
Solution 1:
class Solution {
//Using Variable Size Sliding Window
public int maxSubArray(int[] nums) {
int result=Integer.MIN_VALUE;
int tempMax=0;
int i=0;
int j=0;
while(j<nums.length) {
tempMax+=nums[j];
if(tempMax>result){
result=tempMax;
}
if(tempMax>=0){
j++;
} else{
tempMax=0;
j=j+1;
i=j;
}
}
return result;
}
}
Runtime: 0 ms
Memory Usage: 38.4 MB
Solution link : click here
Solution 2:
class Solution {
public int maxSubArray(int[] nums) {
int maxSoFar=Integer.MIN_VALUE;
int maxEndingHere=0;
int n=nums.length;
for(int i=0;i<n;i++) {
maxEndingHere+=nums[i];
if(maxEndingHere<nums[i]){
maxEndingHere=nums[i];
}
if(maxSoFar<maxEndingHere){
maxSoFar=maxEndingHere;
}
}
return maxSoFar;
}
}
Runtime: 0 ms
Memory Usage: 38.8 MB
Solution link : click here
Solution 3:
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
for(int i=0;i<nums.length;i++){
int sum =0;
for(int
j=i;j<nums.length;j++){
sum += nums[j];
if(sum>max){
max = sum;
}
}
}
return max;
}
}
Runtime: 139 ms
Memory Usage: 41.5 MB
Solution link : click here
Solution 4:
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum =0;
for(int i=0;i<nums.length;i++){
sum
=Math.max(sum+nums[i],nums[i]);
max = Math.max(max,sum);
}
return max;
}
}
Runtime: 2 ms
Memory Usage: 41.5 MB
Solution link : click here
Thank you
0 Comments