Maximum Subarray - Leetcode
Given an integer array
Example:
If anyone had different solution leave it as a comment.
Try this on Leetcode
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
class Solution {
public int maxSubArray(int[] nums) {
int i, j, max1 = 0, max2 = Integer.MIN_VALUE, sum=0;
for(i=0;i<nums.length;i++){
sum = nums[i];
max1 = nums[i];
for(j=i+1;j<nums.length;j++){
sum += nums[j];
if(sum>max2){
max2 = sum;
}
}
if(max1>=max2){
max2 = max1;
}
}
return max2;
}
}
Here we are taking each element and calculating sum till the end. Storing that max value and again repeating previous steps until end of array.
If anyone had different solution leave it as a comment.
Try this on Leetcode
public static int maxSubArray(int[] nums) {
ReplyDeleteint sum=0;
int max=nums[0];
for(int i=0;inums[i]) {
max=sum>max?sum:max;
}
else {
sum=nums[i];
max=nums[i]>max?nums[i]:max;
}
}
return max;
}
//This has O(n) Time complexity. Let me know if my solution can be further optimised.
Thanks for your opinion. It looks like your code has errors in for loop and also there is no If condition. Without If , else cannot be used. Please solve these errors and don't forget to update your solution and try it once on leetcode(question link is given at the bottom of post)
Delete