FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode-solutions-java/53.maximum-subarray.java at main · marklcrns/leetcode-solutions-java · GitHub
marklcrns
/
leetcode-solutions-java
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
1
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode-solutions-java
/
53.maximum-subarray.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
83 lines (78 loc) · 1.47 KB
Breadcrumbs
leetcode-solutions-java
/
53.maximum-subarray.java
Copy path
File metadata and controls
83 lines (78 loc) · 1.47 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
* @lc app=leetcode id=53 lang=java
*
* [53] Maximum Subarray
*
* https://leetcode.com/problems/maximum-subarray/description/
*
* algorithms
* Easy (47.75%)
* Total Accepted: 1.3M
* Total Submissions: 2.8M
* Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
*
* Given an integer array nums, find the contiguous subarray (containing at
* least one number) which has the largest sum and return its sum.
*
*
* 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 * 10^4
* -10^5 <= nums[i] <= 10^5
*
*
*
* 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.
*/
class
Solution
{
public
int
maxSubArray
(
int
[]
nums
) {
if
(
nums
.
length
==
1
) {
return
nums
[
0
];
}
int
sum
=
nums
[
0
];
int
total
=
0
;
for
(
int
i
=
1
;
i
<
nums
.
length
;
i
++){
total
=
total
+
nums
[
i
];
}
Integer
runningSum
=
sum
;
for
(
int
i
=
1
;
i
<
nums
.
length
;
i
++) {
if
(
sum
+
nums
[
i
] <
nums
[
i
]) {
sum
=
nums
[
i
];
}
else
{
sum
+=
nums
[
i
];
}
if
(
sum
>
runningSum
) {
runningSum
=
sum
;
}
}
if
(
runningSum
>
total
) {
return
runningSum
;
}
return
total
;
}
}
Back
|
FazBrowse Home
|
New Git URL