i**********e
发帖数: 1145 | 1 Programming pearls 上有。
二分后要考虑三种可能性：
１）max subarray 完全在左边某部分
２）max subarray 完全在右边某部分
３）两个 subarray 之间交接，左后边某部分和右前边某部分两个结合起来成为 max
subarray.
思路的突破就在于怎么在第三种状况下找出 max subarray. |
|
a***r
发帖数: 93 | 2
The original problem was asking if exist a subarray, I figured it did not
ask for the subarray itself.
Also, it is a subarray, not a sub sequence. |
|
s**********e
发帖数: 326 | 3 dp题，我的思路，大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only ... 阅读全帖 |
|
s**********e
发帖数: 326 | 4 dp题，我的思路，大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only ... 阅读全帖 |
|
S*******C
发帖数: 822 | 5 Subarray Sum
20%
Accepted
Given an integer array, find a subarray where the sum of numbers is zero.
Your code should return the index of the first number and the index of the
last number.
Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
http://www.lintcode.com/en/problem/subarray-sum/
下面的解法总是在第16个test case Memory Limit Exceeded
public ArrayList subarraySum(int[] a) {
ArrayList res = new ArrayList();
//a map between sum and index
Has... 阅读全帖 |
|
I**A
发帖数: 2345 | 6 N*N是个matrix
看过求array的最大subarray
木见过怎么求matrix的subarray，你是说submatrix maybe? |
|
d********w
发帖数: 363 | 7 Given an array of 0's and 1's. only, find the maximum length of the subarray
such that the number of 0's and 1's in that subarray are equal. |
|
S******1
发帖数: 269 | 8 // Find the longest subarray with equal 1 and 0.
public static int[] longestSub(int[] inputArray) {
int length = inputArray.length;
int[][] record = new int[length][length];
//Initial
for (int i = 0; i < length; i++)
if (inputArray[i] == 1)
record[i][i] = 1;
else
record[i][i] = -1;
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (i < j)
... 阅读全帖 |
|
c**j
发帖数: 103 | 9 这个表面简单的题Goolge MS 都考了啊。干脆发给新话题吧，还请大牛们指教啊
2个variation
MS 要求连续位置，考虑duplicate，DP， divide conquer, sort 貌似都有难度。。
Google 没有要求连续位置，简单不少，但是不让sort。。。。。又难回去了
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http://www.careercup.com/question?id... 阅读全帖 |
|
s**********e
发帖数: 326 | 10 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的 |
|
s******n
发帖数: 3946 | 11 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
preSubarray，不能单用一个变量来存presubarray。 |
|
s**********e
发帖数: 326 | 12 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的 |
|
s******n
发帖数: 3946 | 13 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
preSubarray，不能单用一个变量来存presubarray。 |
|
e***s
发帖数: 799 | 14 Find the contiguous subarray within an array (containing at least one number
) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using
the divide and conquer approach, which is more subtle.
想知道O(nlogn)的解法。 |
|
g***j
发帖数: 1275 | 15 给一个array，有正有负，求最大的subarray的和
给一个array，都是正，有大于1的也有小于1的，求最大的subarray的积
这两个题目差不多一样的吧？ |
|
x*******i
发帖数: 26 | 16 给一个array of int，以及一个range (low, high)，找出array中
所有的subarray使得这个subarray的和在range之中。array可以有负数
这个O(N^2),
for i= 0 to N,
for j= i to N
check sum(i, j) is in range. // add num[j] to previous sum(i, j-1)
有更好的方法吗？ |
|
k******z
发帖数: 4 | 17 dp，求出以第i个元素结尾的subarray，之后memoize下来，然后第i+1个元素是以第i个
元素的subarray为基础，加上第i+1个元素的weight，如果仍然符合要求，那么就
memoize，否则就抛弃，这样子只要遍历一次n就解决战斗了，running time是和输出结
果的个数有关，假设输出结果是m，那running time就是O(m + n) |
|
h********8
发帖数: 1 | 18 请教Leetcode Maximum Subarray 如果加两个条件，怎么解：
1. 打印Start和End，这个比较容易。
2. 返回的Subarray的长度要大于1。（追问如果是大于N呢？）
以下是我的大于1的code，各位有没有更好的解法？
public int maxSubWithSizeGreaterThanOne(int[] nums) {
if (nums.length < 2) {
return 0;
}
int maxStart = 0;
int maxEnd = 1;
int start = 0;
int sum = nums[0] + nums[1];
int max = sum;
for (int i=2; i
sum = Math.max(sum+nums[i], nums[i-1]+nums[i]);
if... 阅读全帖 |
|
m******3
发帖数: 346 | 19 没有太明白，算一下每个长度为n的以nums[i]结尾的最大值，如何线性解决？
也是DP么？ 另外我觉得和n=1的情况还是有区别的啊，如果subarray是从nums[i]开始
而不是在已经有的subArray上加上nums[i],对n=1的情况没问题，nums[i]本身就保证了
长度至少大于等于1,但是如果n!=1,这个没办法保证吧，能详细说说么？ |
|
b*****n
发帖数: 618 | 20
这是个sliding window吧
sum[i]表示nums[i]结尾的长度为n的subarray sum
sum[i] = sum[i - 1] - nums[i - n] + nums[i]
dp[i]表示nums[i]结尾的长度>=n的subarray sum最大值
dp[i] = max(sum[i], dp[i - 1] + nums[i]) |
|
c**********e
发帖数: 2007 | 21 Suppose you have an array of integers a[0],...,a[n]. Design an algorithm
to find the maximum sum of any contiguous subarray. Optimize speed. |
|
K******g
发帖数: 1870 | 22 有个一个N*N的array，里面的元素是pos或者neg的整数，求最大的一个所有元素和最大
subarray。 |
|
x***y
发帖数: 633 | 23 find a submatrix with the largest sum, similarly to find a subarray with the
largest sum in an array... |
|
a***r
发帖数: 93 | 24 memory O(n)
time O(nlogn)
//~ Given a array,find out if there exist a subarray such its sum is zero
#include
#include
using namespace std;
static void swap(int *p, int i, int j) {
int t=p[i]; p[i]=p[j];p[j]=t;
}
static int partition(int *p,int left,int right) {
int j=left;
for(int i=left;i
if(p[i]
}
swap(p,j,right);
return j;
}
static void binary_sort(int *p, int left, int right) {
if(left>=r... 阅读全帖 |
|
j********x
发帖数: 2330 | 25 照你本来题目的描述，其实是个很简单的问题
这个题目的描述跟subset sum其实是不同的，你这里是subarray，而不是subset |
|
|
z*********8
发帖数: 2070 | 27 Give an array of positive integers and a target positive integer, find the
continuous subarray whose sum is closest to the target.
谁能给个简洁清晰的代码？ |
|
c*******r
发帖数: 309 | 28 给一个array 都是 positive， 给一个 sum， 输出所有的 subarray 加和是 sum
这题应该咋解？ 用recursion?准备了小半年发现水平依然是菜比。。 |
|
s*******n
发帖数: 97 | 29 题目好像说的是subarray吧？如果是这样,累加求和，然后binary search, O(nlogn) |
|
j********x
发帖数: 2330 | 30 双指针的窗口移动，考虑全是正数，这应该是最直观的解法
subarray和一类的题目可以考虑用prefix array sum的方法在常数时间内求得，这个方
法在很多跟array matrix有关的题目里都用得上
楼上几位能介绍一下dfs怎么做么？ |
|
r**h
发帖数: 1288 | 31 题目不要求subarray是连续的吧
DFS，就是根据每个节点（取或者不取）两种情况向后搜索并记录当前的解。由于题目
里面提到数组中所有元素都是正数，因此如果当前的和已经大于sum那么就可以直接剪枝
void findSubSetSum(int *pArr, int *pSub, int nSize, int nIndex, int curSum,
int nSum){
//剪枝
if(curSum+pArr[nIndex] > nSum)
return;
//找到解
if(curSum+pArr[nIndex] == nSum){
pSub[nIndex] = 1;
printResult(pArr, pSub, nIndex);
pSub[nIndex] = 0;
return;
}
//继续向后搜索，分两种情况
if(nIndex < nSize-1){
pSub[nIndex] = 1;
findSubSetSum(pArr, pSub, nSize, nIndex+1, curSum+pArr[nIndex... 阅读全帖 |
|
z*********8
发帖数: 2070 | 32 一个int array 长度为N, 里面有M 个数字， N >> M
所以这个array大概是这样：
0011111222222333333333333.。。
现在要找出最长的连续重复subarray 比如333333333333， 有什么比较好的方法？ |
|
|
x*******i
发帖数: 26 | 34 有种极限情况，range很大，所有subarray sum都在里面，总数是n^2级别的
这应该是下限吧
★ 发自iPhone App: ChineseWeb 8.2.2 |
|
a*********2
发帖数: 194 | 35 不会。
比如对区间[begin, end)，mid=(begin+end)/2，分段，[begin, mid), [mid, end).
所求区间或者在这两个子段中不胯mid，或者是跨mid的区间。跨mid的区间O(n)找到。
总的复杂度O(n lg n)，详情见introduction to algorithm third edition chapter 1
.4中对subarray的分析。 |
|
b******g
发帖数: 3616 | 36 看了半天没搞明白你在说哪题？没有名字叫sub Mul max的啊？你是在说Maximum
Product Subarray么？。。。。 |
|
b******g
发帖数: 3616 | 37 这道题如果用DP的话个人觉得double和int没什么区别啊？对于每一个A[i]，dp需要已
经记录了以A[i-1]为结尾的subarray的product_min和product_max，然后推算以A[i]本身
为结尾的product_min,product_max必定在product_max*A[i], product_min*A[i]以及A
[i]三个数之间，感觉推广成double并没有影响这个逻辑，即使有(-1,1)的数？ |
|
b*****n
发帖数: 618 | 38 可以继续用DP吧，加个维度就好，subarray的长度 |
|
m******3
发帖数: 346 | 39 这个DP怎么写呢？
定义dp[i][j]为以nums[i]结尾的长度为j的subArray长度
dp[i][1] = nums[i]
dp[i][j] = (dp[i-1][j-1]+nums[i]) if dp[i-1][j-1]!=0;
dp[i][j] = 0; if dp[i-1][j-1]=0
是这样么 ？ |
|
b*****n
发帖数: 618 | 40 貌似也不用。。
只要算一下每个长度为n的以nums[i]结尾的最大值，然后dp长度为>=n的以nums[i]结尾
的最大值就行了，这样线性就能解决。
最开始的largest subarray sum其实是n==1的一种特殊情况，做法是完全一样的。 |
|
c*****m
发帖数: 271 | 41 没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
subarray里面长度最大的那个. |
|
j*****8
发帖数: 3635 | 42 en，你是对的
那就得用求subarray sum来做了 |
|
b*****n
发帖数: 618 | 43 如果是求最长的subarray的话，用TreeMap可以O(nlogn)，
谨慎地认为没有更好的解了。。 |
|
k***i
发帖数: 2 | 44 You're given an array containing both positive and negative integers and
required to find the subarray with the largest sum |
|
k***e
发帖数: 556 | 45 【 以下文字转载自 JobHunting 讨论区 】
发信人: krone (krone), 信区: JobHunting
标 题: 讨论个subarray sum的变种问题
发信站: BBS 未名空间站 (Sun Nov 29 09:27:08 2009, 美东)
input: a circular array
output: a subvector of the array that has max sum
可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
我的想法是
1. take any element as the leader and break the circle into one dimensional
array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle
passes a[1]. in the next step we will fig |
|
j*****u
发帖数: 1133 | 46 这个挺简单的，不要想复杂了
写了个int[][]的，如果要求任意type T可以在Serialize和Deserialize传入Write(T)和
Read(T)的delegate或者interface，因为serializer不可能知道如何读写任意一个type
// Test code
static void Main(string[] args)
{
var array = new int[][] { new int[] { 2, 6, 35 }, new int[] { 0 }, new int[] { 3, 76 } };
string file = @"C:\data.bin";
using (FileStream fs = new FileStream(file, FileMode.Create, FileAccess.Write))
{
Serialize(array, fs);
}
using (FileStream fs = new FileStream(file, FileMode.Open, File... 阅读全帖 |
|
L***Q
发帖数: 508 | 47 据称是facebook面试题，大意如下：
给一个int array，找出最长的递增的contiguous subarray。算法worst case是O（n）
，如何提高average 的效率。
算法我想了一个：给定array A，从左到右扫描。最初起点为A[0]找出递增的
contiguous subarray，假设结束与A[k-1]。然后以A[k]为起点扫描下一个递增的
contiguous subarray。worse case为O(n)。
关于如何提高average效率，我想到2个策略：
1. 如果剩下未扫描部分小于当前最长的递增的contiguous subarray，那剩下不用扫描
了；
2. 假设当前最长递增的contiguous subarray长度为k，接下来的扫描起点是A[i]，那
么首先比较A[i+k]和A[i+k+1]，如果A[i+k]大于A[i+k+1]，那么跳过A[i]到A[i+k]，以
A[i+k+1]作为扫描起点。因为如果A[i+k]大于A[i+k+1]，从A[i]开始的递增的
contiguous subarray长度最多为k，那可以不用扫描。
第二个... 阅读全帖 |
|
l***i
发帖数: 1309 | 48 max production subarray
1. we can see the array as subarrays delimited by 0, and each of those
subarrays can be processed indepdent of each other.
2. For each subarray without 0, if the count of negative elements is even,
then the value of this subarray is the product of all elements. If the count
of negative elements is odd, then we need to throw away one negative
element, this one is either the leftmost negative element, or the rightmost
negative element.
input: int A[], int N;
// assume empty... 阅读全帖 |
|
c*********i
发帖数: 46 | 49 http://www.geeksforgeeks.org/counting-inversions/
给出了代码，可是看了程序后， 有点不解，想请大牛指教一下：
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
不应该是：
inv_count = inv_count + (mid - i)+1？
当copy a[j]时，left array 剩下的都是inversion,不应该是（mid - i）+ 1 个吗？
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /*... 阅读全帖 |
|
b*********e
发帖数: 26 | 50 第二题这个方法有可能吗？
先求sum，w/o loss of generality, assume sum>0
然后从两端加逼，如果两端有>0的数，去掉一个使得|sum|最小，然后继续
如果两端都小于0，就一起往里扫算subarray sum，直到碰到subarray sum>0的时候停
止，去掉subarray sum可以mininize |sum|的那个subarray
sum<0的情况同理
过程中记录|sum|最小的时候的subarray |
|
