Skip to content

Instantly share code, notes, and snippets.

@rezaiyan
Last active April 1, 2019 07:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rezaiyan/cdc3a486e7b80ae83959d2be29181173 to your computer and use it in GitHub Desktop.
Save rezaiyan/cdc3a486e7b80ae83959d2be29181173 to your computer and use it in GitHub Desktop.
Maximum sum of a sub-array
//Given an integer array nums,
//find the contiguous subarray (containing at least one number)
//which has the largest sum and return its sum.
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1)
return nums[0];
int sum = 0;
int answer = nums[0]; //Initial value of #ans is first element of array
for (int value : nums) {
if (value > sum && sum < 0)
sum = value;//The beginning of sub-array
else
sum += value;
answer = Math.max(answer, sum);
}
return answer;
}
}
@farsialgorithm
Copy link

The overal algorithm seems correct and with log(N) complexity.
I am not sure if you need to do the checking for the specific case of positive values. Can you please remove that part and give it a try?
Try to minimize the code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment