GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — leet-code/Java/Minimum Subarray.java at master · awangdev/leet-code

Expand file tree

/

Minimum Subarray.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
81 lines (68 loc) · 2.4 KB
/

Minimum Subarray.java

Copy path

File metadata and controls

executable file
·
81 lines (68 loc) · 2.4 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
E
1532126087
tags: Greedy, Array, DP, Sequence DP, Subarray
time: O(m)
space: O(1)
给一串数组, unsorted, can have negative/positive num. 找数组中间 subarray 数字之和的最小值
#### DP
- 看到 min value, 至少考虑dp:
- Consider last num: min sum will be (preMinSum + curr, or curr)
- Use preMinSum to cache previouly calcualted min sum, also compare with +curr.
- Have a global min to track: because the preMinSum can be dis-continuous.
- 也可以写成 dp[i] 但是没什么必要
```
/*
Given an array of integers, find the subarray with smallest sum.
Return the sum of the subarray.
Example
For [1, -1, -2, 1], return -3
Note
The subarray should contain at least one integer.
Tags Expand
Greedy LintCode Copyright Subarray Array
*/
/*
DP, Sequence DP
Consider last num: min sum will be (preMinSum + curr, or curr)
Use preMinSum to cache previouly calcualted min sum, also compare with +curr.
Have a global min to track: because the preMinSum can be dis-continuous.
*/
public class Solution {
public int minSubArray(List<Integer> nums) {
if (nums == null || nums.size() == 0) return Integer.MAX_VALUE;
int preMinSum = 0, min = Integer.MAX_VALUE;
for (int num : nums) {
preMinSum = Math.min(num, preMinSum + num);
min = Math.min(min, preMinSum);
}
return min;
}
}
/*
Thoughts:
Note: sub-array has order. It's not sub-set
1. On each index: decide to add with nums.get(i), to use the new lowest value nums.get(i). That means:
If the new value is negative (it has decresing impact on sum) and the sum is larger than new value, just use the new value.
In another case, if sum has been nagative, so sum + new value will be even smaller, then use sum.
2. Every time compare the currMin with the overall minimum value, call it minRst.
Note: remember to pre-set init value for curMin, minRst.
*/
public class Solution {
/**
* @param nums: a list of integers
* @return: A integer indicate the sum of minimum subarray
*/
public int minSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int curMin = nums.get(0);
int minRst = nums.get(0);
for (int i = 1; i < nums.size(); i++) {
curMin = Math.min(nums.get(i), curMin + nums.get(i));
minRst = Math.min(curMin, minRst);
}
return minRst;
}
}
```
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.