Java Exercises: Find a contiguous subarray with largest sum from a given array of integers
Java Basic: Exercise-122 with Solution
Write a Java program to find a contiguous subarray with largest sum from a given array of integers.
Note: In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
The subarray should contain one integer at least.
Pictorial Presentation:
Sample Solution:
Java Code:
public class Main {
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.print(max_SubArray(nums));
}
public static int max_SubArray(int[] nums) {
if (nums.length < 1) {
return 0;
}
int max = nums[0];
int max_Begin = 0;
int max_End = 0;
int begin = 0;
int end = 0;
int sum = 0;
while (end < nums.length) {
sum += nums[end];
if (sum < 0) {
sum = 0;
begin = end + 1;
} else {
if (sum > max) {
max = sum;
max_Begin = begin;
max_End = end;
}
}
end++;
}
return max;
}
}
Sample Output:
6
Flowchart:
Java Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a Java program to reverse a given linked list.
Next: Write a Java program to find the subarray with smallest sum from a given array of integers.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
Java: Tips of the Day
How to sort an ArrayList?
Collections.sort(testList); Collections.reverse(testList);
That will do what you want. Remember to import Collections though!
Ref: https://bit.ly/32urdSe
- New Content published on w3resource:
- HTML-CSS Practical: Exercises, Practice, Solution
- Java Regular Expression: Exercises, Practice, Solution
- Scala Programming Exercises, Practice, Solution
- Python Itertools exercises
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework